RSA暗号(弊研究室の某課題について考える20日目)
はじめに
失踪は許さない弊研究室の某課題について考えるの20日目の記事です。
他の記事も徐々に書いていますが完結は年明けになりそうです。
RSA暗号
RSA暗号は桁数の大きい合成数の素因数分解は難しいという理論の元で構成された公開鍵暗号です。
共通鍵暗号と公開鍵暗号
暗号方式には共通鍵暗号と公開鍵暗号があります。共通鍵暗号は暗号化と復号に同じ鍵を用います。公開鍵暗号では公開鍵と秘密鍵の2種を用意し、片方の鍵で暗号化したものはもう片方の鍵でしか復号できないといったものとなります。
共通鍵暗号では暗号化と復号に要する鍵が同じであるため鍵を安全に相手に渡す必要があります。
一方で公開鍵暗号では秘密鍵は自身でもっておくものであるため、公開鍵等の情報を用いて秘密鍵を推測、生成されないようなアルゴリズムである必要があります。
RSA暗号の仕組み
- 素数pとqを選びます。
n=p*q,φ(n)=(p-1)*(q-1)とするφ(n)と互いに素となるeを選ぶd * e ≡ 1 (mod φ(n))となる最小のdを選ぶnとeを公開鍵、p,q,dを秘密鍵とする
RSA暗号鍵を使った暗号化と復号
2つの方法で暗号化・復号を行いたいと思います。
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は超えるはずなのであとは上の時と同じように復号してください。
