ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

NITAC minictf

参加しとらん

馬刺し美味かった.

 

作問した -解説-

1問だけ.

crypto_300_blind

僕の草案から少し変わってるかもしれないので適宜読み替えてください(問題見てないのでわからん すまん 馬刺しは美味かった). 

 

crypto_300_blind

元ネタはこれ

Blind signature - Wikipedia

 

RSAで 攻撃対象の公開鍵{e, N}と秘密鍵d, 解読したい暗号文c, 暗号文cに対応する平文m

があるとして, 

 

1. 攻撃者が好きな数字rを公開鍵{e, N}を使って暗号化 (r_cとする)

2. 暗号化した r_c と 暗号文 c を 掛ける (s とする)

3. 攻撃対象にsを送りつけて秘密鍵dで署名してもらう 

4. 署名から平文が得られる

 

こんな感じの攻撃手法

 

-前提-

c ≡ m^e mod N

m ≡ c^d mod N 

N = p * q ; where p and q are sufficiently large

 

-証明-

好きな数字 r を公開鍵{e, N} で暗号化 : r_c

r_c ≡ r^e mod N

 

c と r_c を掛ける : s

s ≡ c * r_c mod N

 

s はさらに以下のように表される

s ≡ m^e * r^e mod N 

  ≡ (m*r)^e 

 

s を 秘密鍵 d で署名してもらう 

 

s^d mod N = (m*r)^ed mod N

s^d ≡ m*r mod N  

これで平文に1. で選択した数字rを掛けたものが得られた.

あとは Nを法としたrの逆元をm*r に掛けてあげると平文mが降ってくる.

 

 

今回の問題は

1. 2つの数字x1, x2を自分で決める

2. pow(x1, x2, n) * c を復号したものが返ってくる

 

といった感じになっている(はず),

 

これは

s ≡ (x1^x2 mod N * m^e mod N) mod N

≡ x1^x2 * m^e mod N

 

になって, s を d で署名するので

s^d ≡ x1^(x2*d) * m^(ed) mod N 

≡ (x1^(x2*d) mod N * m mod N) mod N

 

 

このとき x2 = e であれば

s^d ≡ x1 * m mod N

となる

 

あとは邪魔なx1を消せばよいので, x1の逆元(x1^-1)を掛けてあげると

x1 * x1^-1 * m mod N 

≡ m mod N 

 フラグが得られる

 

 

x1 = なんでもいい (ただし逆元が存在する数字)

x2 = e = 65537

 

 

おわりに

最近しずりん(静凛 (@ShizuRin23) | Twitter)がめっちゃ好き

どうすればいいかわからん ほんまかわいい