RSA暗号をわかりやすく解説
ブラウザーに南京錠のマークが表示されるとき、メッセージに署名するとき、ソフトウェアが更新を確認するとき、そこでは公開鍵暗号が働いており、RSA はその最もよく知られた形です。その考え方は、メッセージに鍵をかける鍵は公開してもよく、それを開ける鍵だけを秘密にしておく、というものです。驚くべきことに、この仕組み全体は学校で習う算数、つまり素数、掛け算、余りの上に成り立っています。
RSA が解決する問題
カエサル暗号から現代の AES まで、それまでの暗号は鍵をかけるのにも開けるのにも同じ鍵を使うので、双方はまず秘密の鍵をひそかに共有しなければなりません。公開鍵暗号はその手順をなくします。各人は2つの鍵を持ちます。誰もがその人宛てのメッセージを暗号化するのに使える公開鍵と、その人だけが持ち、それだけが復号できる秘密鍵です。ホイットフィールド・ディフィーとマーティン・ヘルマンが1976年にこの考え方を示し、その1年後、マサチューセッツ工科大学(MIT)のロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンが実現方法を見つけ、3人の頭文字から RSA と名付けられました。
鍵を作る
2つの大きな素数 p と q を選んで掛け合わせます。n = p × q です。オイラーのφ関数 φ(n) = (p − 1)(q − 1) を計算します。これは n より小さく n と共通の因数を持たない数の個数です。φ(n) と共通の因数を持たない公開指数 e を選びます。通常は65537が選ばれます。次に、e × d を φ(n) で割った余りが1になるような秘密指数 d を求めます。拡張ユークリッドの互除法を使えばすぐに求められます。公開鍵は組 (e, n)、秘密鍵は d です。p = 61、q = 53 なら、n = 3233、φ(n) = 3120、e = 17、d = 2753 となります。
暗号化と復号
メッセージはまず n より小さい数 m に変換されます。暗号化するには c = mᵉ mod n、つまり mᵉ を n で割った余りを計算します。復号するには cᵈ mod n を計算します。e × d は φ(n) の倍数より1大きいので、これで m に戻ることがオイラーの定理によって保証されます。上の鍵では、文字 A(コード65)は 65¹⁷ mod 3233 = 2790 になり、2790²⁷⁵³ mod 3233 = 65 で元に戻ります。これほど大きなべき乗は決して書き出されません。繰り返し二乗法が、指数の1ビットごとに1回二乗し、各ステップで余りをとって計算します。
デジタル署名
RSA は逆向きにも使えます。メッセージを秘密指数でべき乗した s = mᵈ mod n は、鍵の持ち主にしか作れない署名になります。誰でも公開鍵でそれを確認できます。sᵉ mod n で m に戻れば、メッセージは d の持ち主から来たもので、途中で改ざんされていません。実際に署名されるのは、メッセージそのものではなく、メッセージの短いハッシュ値です。このような署名が、ソフトウェアの更新、安全なウェブサイト、電子文書を守っています。
安全である理由
n と e は誰にでも見えます。d を求めるには φ(n) が必要で、φ(n) を求めるには p と q が必要なので、RSA を破ることは n を素因数分解することに帰着します。コンピューターにとって2つの素数を掛けるのは1マイクロ秒にも満たない作業ですが、その積を元の2つに分解するのは極めて難しいと考えられています。これまでに素因数分解された最大の RSA チャレンジ数は2020年の RSA-250 で、829ビットあり、計算機時間でおよそ2700年かかりました。現在使われている鍵は少なくとも2048ビット、約617桁です。
二度発見された秘密
RSA の4年前の1973年、英国の数学者クリフォード・コックスは、情報機関 GCHQ で働いていたときに、同僚ジェームズ・エリスのアイデアをもとに同じ方式を見つけていました。この研究は機密扱いとされ、1997年になってようやく公開されました。RSA 自体は1983年に米国で特許を取得しました。特許は2000年9月に失効しましたが、その2週間前にアルゴリズムはパブリックドメインとして公開されていました。
実際の RSA
実際の RSA では、テキストを直接暗号化することはありません。OAEP などの方式でメッセージにランダムなバイトをパディングし、同じメッセージでも毎回違う形で暗号化され、パターンが漏れないようにします。RSA は遅いので、主に AES のような高速な共通鍵暗号の短い鍵を交換したり保護したりするため、あるいは署名のために使われます。十分に大きな量子コンピューターがあれば、1994年のショアのアルゴリズムで n をすばやく素因数分解できるため、新しい耐量子計算機暗号の方式が RSA と並行して導入されつつあります。
試してみましょう
RSA暗号デモを開いて、自分の素数や2〜8桁のランダムな素数から鍵を作り、拡張ユークリッドの互除法が1行ずつ d を求める様子を見て、メッセージを1文字ずつ暗号化または署名し、好きな文字の繰り返し二乗法をたどってみましょう。それからイブに n を素因数分解させ、必要な時間が素数の大きさとともにどう増えるかを見てください。
よくある質問
なぜ RSA には素数が必要なのですか?
φ(n) を簡単に計算できるのは、n がどんな素数に分解されるかを知っているときだけだからです。p と q が素数で n = p × q なら、φ(n) = (p − 1)(q − 1) です。また、素数を使うと n には小さな因数がまったくないので、その大きさの数としてはできるだけ素因数分解しにくくなります。
なぜ e は65537であることが多いのですか?
65537 = 2¹⁶ + 1 は素数で、2進数では1が2つしかないので、これで暗号化するには16回の二乗と1回の掛け算だけで済みます。また、3のような非常に小さな指数の弱点を避けられるだけの大きさもあります。
RSA とディフィー・ヘルマンの違いは何ですか?
ディフィー・ヘルマンは、2人が公開の通信路で共有の秘密鍵を取り決められるようにするもので、それ自体では何も暗号化も署名もしません。RSA は鍵ペアで直接暗号化と署名を行います。どちらも一方向には簡単で逆方向には難しい問題に基づいています。RSA は素因数分解、ディフィー・ヘルマンは離散対数です。
デモの鍵は本物の暗号化に使えますか?
いいえ。素数は最大でも12桁程度なので、作られる鍵はどれも数秒以内に素因数分解でき、しかも各文字をパディングなしで個別に暗号化します。RSA の仕組みを見るためのもので、何かを守るためのものではありません。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
RSA暗号デモを開く