前回の記事「世界最小のRSA鍵ペアは何bitか」でp=3, q=5(つまりn=15)の場合のRSA鍵ペアを紹介しましたが、kazuhookuさんからこんなブックマークコメントを頂きました。 面白い。n=4(あるいは2)はダメなのかな もっと小さいnを採用できないのか?という指摘かと思います。前回記事では普段のRSA暗号のノリで「p,qは異なる奇素数」という前提を置いていましたが、既に非常識なくらい短い鍵長の話をしている中で常識にとらわれるのは無意味というものでしょう。 本稿では15未満のnでRSA暗号らしきものが構成できるのかどうかを探ります。 n=1の場合 RSA暗号の平文mに対して m^(e*d) = m (mod n)が成り立つ最小のnを考えると、n=p=q=e=d=1が見つかります。これは1bit RSA鍵ということになりますので、もし認められるなら世界最小なのは間違いありません。