RSA暗号(弊研究室の某課題について考える20日目)

はじめに

失踪は許さない弊研究室の某課題について考えるの20日目の記事です。

他の記事も徐々に書いていますが完結は年明けになりそうです。

RSA暗号

RSA暗号は桁数の大きい合成数素因数分解は難しいという理論の元で構成された公開鍵暗号です。

共通鍵暗号公開鍵暗号

暗号方式には共通鍵暗号公開鍵暗号があります。共通鍵暗号は暗号化と復号に同じ鍵を用います。公開鍵暗号では公開鍵と秘密鍵の2種を用意し、片方の鍵で暗号化したものはもう片方の鍵でしか復号できないといったものとなります。

共通鍵暗号では暗号化と復号に要する鍵が同じであるため鍵を安全に相手に渡す必要があります。

一方で公開鍵暗号では秘密鍵は自身でもっておくものであるため、共通鍵等の情報を用いて秘密鍵を推測、生成されないようなアルゴリズムである必要があります。

RSA暗号の仕組み

  1. 素数pとqを選びます。
  2. n=p*q, φ(n)=(p-1)*(q-1)とする
  3. φ(n)と互いに素となるeを選ぶ
  4. d * e ≡ 1 (mod φ(n))となる最小のdを選ぶ
  5. neを公開鍵、p,q,d秘密鍵とする

RSA暗号鍵を使った暗号化と復号

2つの方法で暗号化・復号を行いたいと思います。

  1. opensslコマンドを利用してRSAの公開鍵と復号鍵を作成して暗号化・復号する
  2. 素数pとqを作成し、自力でRSA暗号鍵を作成して文書を暗号化・復号する

opensslコマンドを利用する

まずは暗号鍵を作ります

$ openssl genrsa > server.key # 秘密鍵の作成
$  openssl rsa -in server.key -pubout -out publick-key.pem # 公開鍵の作成

opensslコマンドの秘密鍵には素数pとqが含まれているので公開鍵を作成することが可能です。 openssl rsa -text -in server.keyで確認できます。

ではこの鍵を用いて暗号化していきます

暗号化にはopenssl rsautl -encryptを用います

$ echo "This is a plain text" > plain
$  openssl rsautl -encrypt -pubin -inkey public-key.pem -in plain -out encrypt
]$ cat encrypt
N▒-9U▒
▒▒%`▒;▒▒▒1▒▒=%2u'm▒▒
                    ▒▒֡▒L7▒돆▒▒▒m▒▒W▒▒@T▒
▒L
V▒rU▒▒▒@we▒▒▒-@<▒▒^▒▒▒H▒v▒|^Й▒▒1▒▒{&j*▒GFZ|t▒Q▒▒W{▒▒Q.▒%▒▒▒
                                                           ▒
V▒▒4▒|u▒▒▒Q▒V
▒5▒i▒viyk▒▒![M▒▒,▒ȥh▒▒Ȉ6묛▒▒ң▒l\d▒#▒Dt.▒D̃)sdZ%o}tS`▒▒0▒▒q

次に復号です。復号にはopenssl rsautl -decryptを使います

$  openssl rsautl -decrypt -inkey server.key -in encrypt
This is a plain text

さてでは作った鍵をpythonを用いて暗号化・復号していきます。CTFではよくpythonスクリプト書きますからね

pythonでopensslで作成した鍵を取り扱う

pycryptoライブラリを使用します。

$ sudo pip install pycrypto

こんな感じで暗号化・復号ができます

from Crypto.PublicKey import RSA

with open("encryptpy.txt","w") as f:
    f.write(RSA.importKey(open("public-key.pem").read()).encrypt(open("plain").read(),"")[0])

with open("decrypt.txt","w") as f:
    f.write(RSA.importKey(open("server.key").read()).decrypt(open("encryptpy.txt").read()))

ちなみにopensslコマンドで作成したencryptファイルの復号もできます。

>>> from Crypto.PublicKey import RSA
>>> privkey = RSA.importKey(open("server.key").read())
>>> privkey.decrypt(open("encrypt").read())
'\x02\xb9\x9c\x19\xef~\'\xd9\x93\xa6}2#"\xf0oMH\x86\x9d\x83\x98\xf2M\xda\x97\xdbT\xa9WW_\xb7y\xb8\x03\x1a\xf7P\xc5\xbe\x92\n\xf9^aOA\xae\xe4\xea{\x03?\xaf\x8dX\xe2\xc1Oe\xf8\xa0Z\x96\x87[\x87\xfc\xe2F\x13\xf7u\xd1\xd5sDO\xf7\x11\xef\xc3\x0c\x17\xd3\xa8\x03\xa4t\xd0\xa4O\xdezA?\x04\x01cM\xb8\xb7\xa3y6\xbd\xab\xb6\xf6j\x13\xef\n/\rR\x956\xeffD\x1e01M\x13{\x16\x11\xde\xad\xc5\x18\xbcN\x99\x99F\x85\x99(\x0f\x0byE\xb0\x91\xa0\xd2V_\x90\xc2\x97xG\x05\xc8\xacd\x0e&\x996\x8fl\xbe\xb7\xde\xfb\xc1\x1c\xea,\r\xf7\xa7\x86\x87`\x8fD:\xd0\xd4\x9e\xb1\xd4*Q\xc6\xf7\x1d\x14\xeb?\xccA\xee\xbd\xb1\x82>\x08\ry\xde\xe4\xa2\xd2\xc8\xb3\x7f\xb6e\xc1\xf1\xa3\xbcDa\xae_e)\x19P\x94\xf7\xdep@\x00This is a plain text\n'

しっかり復号できていることが確認できます

pythonで自分で鍵を作成する

RSAアルゴリズムに従ってpythonで鍵を作成します。今回素数p,qは簡単なものを利用します。

from Crypto.PublicKey import RSA
from fractions import gcd

p = 661
q = 821
e = 65537

N = p*q
L = (p-1)*(q-1)

for i in range(2,L):
    if (e*i) % L == 1:
        D = i

key = RSA.construct(map(long,(N,e,D)))
print key.exportKey()
$ python makersa.py
---BEGIN RSA PRIVATE KEY-----
MCUCAQACAwhH2QIDAQABAgMD6qECAgKVAgIDNQICAlECAQ0CAgGZ
-----END RSA PRIVATE KEY-----

ということで秘密鍵が作成できました。鍵サイズが1024bitないのでpycryptoで暗号化・復号はできません。CTFの問題なら1024は超えるはずなのであとは上の時と同じように復号してください。

終わりに

次はplain RSAに対する攻撃という題でRSAのいけない運用に対して話していこうかなと思います。