「メモ」カテゴリーアーカイブ

サマーウォーズのあの暗号を解こう！（その4）

投稿日時: 投稿者:
返信

こちらの続き。
素因数分解（素数とは言ってない）ができたので、秘密鍵Dを求めることにした。

ググったところ、QUANONさんが「Python で公開鍵暗号アルゴリズム RSA を実装してみる」という記事を書いていらっしゃるのでありがたく使わせていただく。

続きを読む →

サマーウォーズのあの暗号を解こう！（その3）

投稿日時: 投稿者:
返信

こちらの続き。
秘密鍵N（=pq）がとある数字で割り切れた。大きな方の値（前の記事ではqとした）が素数なのかどうか、という件。

ミラー・ラビン素数判定法をググったらPythonの実装サンプルが見つかったのでありがたく使わせていただくことにする。

Miller–Rabin(ミラーラビン)素数判定法について理解したい
https://qiita.com/zu_rin/items/25521b5870389e0f85bf

続きを読む →

サマーウォーズのあの暗号を解こう！（その2）

投稿日時: 投稿者:
返信

こちらの続き。
残念ながら期待通りには暗号化できなかった。
E（公開鍵の片割れ）が間違っているのか、M（平文）が間違っているのか…

となると、N（=pq）を素因数分解するしかないだろう。
ある意味正攻法。しかし、3777ビットの整数の素因数分解…

できないよね…

やってみた。

続きを読む →

サマーウォーズのあの暗号を解こう！

投稿日時: 投稿者:
返信

RSA-129は無事解けた暗号化できたので、次は映画「サマーウォーズ」のあの暗号を解いて暗号化してみよう。

「サマーウォーズ」の暗号は暗号文Cと公開鍵の片割れN（=pq）のみが示されていて、公開鍵のもう一つの片割れであるE（暗号化の時の指数）は明示されていないそうだ。
困ったな。ダメ元で3、9007、65537あたりを試すしかないか。

続きを読む →

RSAで遊ぼう

投稿日時: 投稿者:
返信

遊んでみる。
遊びなのでキーは32bitでよい。（30以下だとエラーになった。31以上でOK）

$ openssl genrsa 32 | tee private.key
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MCsCAQACBQC/gCgdAgMBAAECBFTpNXECAwD12wIDAMdnAgJ5LQICcT8CAh4/
-----END RSA PRIVATE KEY-----
$ openssl rsa -text < private.key
Private-Key: (32 bit)
modulus: 3212847133 (0xbf80281d)
publicExponent: 65537 (0x10001)
privateExponent: 1424569713 (0x54e93571)
prime1: 62939 (0xf5db)
prime2: 51047 (0xc767)
exponent1: 31021 (0x792d)
exponent2: 28991 (0x713f)
coefficient: 7743 (0x1e3f)
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MCsCAQACBQC/gCgdAgMBAAECBFTpNXECAwD12wIDAMdnAgJ5LQICcT8CAh4/
-----END RSA PRIVATE KEY-----

続きを読む →