世界最小のRSA鍵ペアは何bitか - hnwの日記

「理論上最短のRSA鍵の鍵長は何ビットなのか？」という疑問が湧いてきたので、RSA鍵の長さに関する制約について調べてみました。とにかく小さいRSA鍵ペアを作ろうと思ったらp=3,q=5の4bit RSA鍵というのが作れそうですが、本当にそんな鍵が作れるのでしょうか？ 本稿ではRSA暗号およびRSA署名のパディングに関する仕組みを紹介し、最短の鍵長となるRSA鍵について検討します。 RSAES-PKCS1-v1_5 におけるパディング 鍵長最短となるRSA鍵ペアを作る上で障害になるのが、RSA暗号のパディングと呼ばれる仕組みです。 RSA暗号における暗号化および復号処理は整数の累乗演算ですから、仮に平文mが1だった場合、暗号文も1ということになってしまい暗号として機能しなくなってしまいます。このような問題への対策として、受け取った平文をそのまま使うのではなく、パディング文字列を付加して暗号化

[kazuhooku]

面白い。n=4（あるいは2）はダメなのかな

[Jxck]

面白い。筆算で解ける暗号、勉強用には良さそう。

[rryu]

n=pqでpとqは異なる素数だからnが小さいとそれだけで鍵が決まってしまうのか。

[key_amb]

実用性は抜きにして、短い鍵を作ろうと思えば作れる、と。

[progrhyme]

実用性は抜きにして、短い鍵を作ろうと思えば作れる、と。

[sho]

面白いことするなー。CTFの問題とかにも良さそう。

[jovi0608]

RSA署名はOID長の差を入れてもmd5WithRSAEncryption(とmd2)の方がsha1より１バイト小さくなると思う。NULL抜きならまだいける？/CC @kjur

[UDONCHAN]

興味深い

[rightgo09]

おもしろい

[p260-2001fp]

『世界最小の鍵ペアである4bit RSA鍵がOpenSSLで動作した（全く実用的ではない）』おもしろかった

[solidstatesociety]

”実際に使うのであれば2048bit以上の鍵を使ってください。”