###### tags: `CTF` `ACSC2021` `crypto`
# RSA stream

Writer :
[top](https://hackmd.io/S0VbDw_7RzyLCEr16S1Rxg)

Problem
---
I made a stream cipher out of RSA! But people say I made a huge mistake. Can you decrypt my cipher?
`chal.py`

import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse
from Crypto.Util.Padding import pad

from flag import m
#m = b"ACSC{<REDACTED>}" # flag!

f = open("chal.py","rb").read() # I'll encrypt myself!
print("len:",len(f))
p = getStrongPrime(1024)
q = getStrongPrime(1024)

n = p * q
e = 0x10001
print("n =",n)
print("e =",e)
print("# flag length:",len(m))
m = pad(m, 255)
m = bytes_to_long(m)

assert m < n
stream = pow(m,e,n)
cipher = b""

for a in range(0,len(f),256):
  q = f[a:a+256]
  if len(q) < 256:q = pad(q, 256)
  q = bytes_to_long(q)
  c = stream ^ q
  cipher += long_to_bytes(c,256)
  e = gmpy2.next_prime(e)
  stream = pow(m,e,n)

open("chal.enc","wb").write(cipher)

Output
---
`chal.enc`

m^�v�9����~�̲(�A�bCw8��vM[��;��\�;��S�G�6=֊�gO.p�]��`uV�~�}�nQ9U�j��<�^6B���2�P��!�7'>�,�;��]8H��GH\�hi���q<�s
7p����q�Κ�Hg*Z��}S��Q�c�r�� v�M�6���0�L8rü���BҗY�Nl-�Xb�w���S� �Bf+sU¤R&`�y
;���E
�{�1.���NW!X0��&�S퉦�ѡt<3���y0c��*�c�,/&p���������U�[�P�{׶ɪ(�v�V�iOz�S�p�w��>�o�/D(3�����Y� �+FEk����_����3��|0�vh��Ā*���g0��Ki%g+�V�>���z����z�/�Y��X�w�ޅ��Նp$a����e����&���M),��C��`�����ڧ����U2��\$�$��}f�N�Stp'�?`�W[u�(�v(�_Ρz���^5���b	����+�~�����_J��A��](=�d��U�%�7�sP�o�^X��1$4
G�ٜ��S�gY�m
�y:L��.-F�:T>ٿ��ԧ]�ǖ+�PL
�I��l]j��o<l��
��$)
"��
7q:��N��wwoۑ�B��ǥ�c%#I��+��ط��Y��_���Ez�Bkl��g��XP�/�,<���F�eN�ܶ���^kD6�=�����H\J�w+mm0���gJ$Ft\���q�H,�����A�&b==�����R�}}�k

`output.txt`

len: 723
n = 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453
e = 65537
# flag length: 97

Solve
---
バカみたいなミスをして時間を取られてしまった問題 :-1:
この問題は普通のRSA暗号をStream暗号っぽくしたもので、よく見るとRSA暗号の脆弱性の一つである**Common Modulus Attack**が適用できる.

`chal.py`では`chal.py`自身を読み込み、それを256byteずつのブロック`q`にしている.
また、1024bitの素数p,qを生成し、RSAの公開鍵を$n=p*q$と`e=0x10001`として、flagを平文として暗号化している.
できた暗号文を`stream`として、`q`とXORをしたものを`cipher`に連結していく
次のブロックでは`stream`を生成する際に`0x10001`の次の素数を`e`として暗号化している.
ここがポイントで、同じ平文、同じ法に対して異なる暗号化指数`e`で暗号化するというミスを犯している.
このような場合は**Common Modulus Attack**が適用できてしまう.
下に上記のミスをした際にCommon Modulus Attackで`m`を復元できる証明を示す.

---
### Common Modulus Attack
同じ平文`m`を異なる暗号化指数`e1,e2`と,同じ法`n`で暗号化した暗号文が２つ入手可能とする.
$$
c_1 = m^{e_1} \mod n\\
c_2 = m^{e_2} \mod n
$$
ここで、$gcd(e_1,e_2)==1$を満たすので、拡張ユークリッドの互除法より
$$
e_1s_1+e_2s_2=1 \leftarrow extgcd(e_1,e_2)
$$
となる$(s1,s2)$がただ１つ見つかる.
$$
\begin{eqnarray}
c_1^{s_1}*c_2^{s_2} &=& m^{e_1s_1}*m^{e_2s_2}\mod n\\
&=&m^{(e_1s_1+e_2s_2)} \mod n\\
where, e_1&s_1&+e_2s_2=1 \\
&=&m^1 \mod n \\
&=&m
\end{eqnarray}
$$
以上より$m$が求められる.

---
問題に戻り`cipher`の中身を考えると以下のようになっている.
$$
\begin{eqnarray}
cipher = c_1 \oplus q_1 | c_2 \oplus q_2 | c_3 \oplus q_3
\end{eqnarray}
$$
ここで、$q_1,q_2,q_3$は既知なので、それぞれにもう一度`XOR`をしてあげることで
$$
\begin{eqnarray}
cipher = c_1 | c_2 | c_3
\end{eqnarray}
$$
とすることができる.
暗号化指数`e`も最初の`0x10001`から次の素数を新たな`e`として選択しているので、それぞれの`e`を求めることができる.
これで,同じ平文`m`を異なる暗号化指数$e_1,e_2,e_3$で暗号化している暗号文$c_1,c_2,c_3$が揃ったのでどれか２つに対して**Common Modulus Attack**を適用することで`flag`を得ることができる.

ちなみにバカみたいなミスとは`XOR`の`^`を冪乗の記号だと勘違いしたことです。ありがとうございました :+1:

---
:tada:`ACSC{changing_e_is_too_bad_idea_1119332842ed9c60c9917165c57dbd7072b016d5b683b67aba6a648456db189c}`