「RSA公開鍵暗号」 素数が役に立つとき

暗号を作る方法にRSA公開鍵暗号系というものがあります。この方法は、各自が1対の暗号化鍵と復号鍵を持っています。そして、暗号鍵をみんなが見れるように公開します。復号鍵は秘密にして各自が保管しておきます。文章の送信者は受信者の暗号化鍵をわかっていますから、それを使って暗号化します。受信者は暗号文を受け取り、自分の持っている復号鍵を使って元の読める文章にします。仕組みはざっくりとこんな感じです。では、素数がどう使われてるんでしょうか。

この方法には3つの素数が必要です

暗号化鍵Pは整数の対( N, p ), 復号鍵Sは整数の対( N, s )でsは秘密にします。N、s

、pは非常に大きい整数である必要があります。Nは200桁、s, pは100桁ほどのものが使われるそうです。Mを平文とすると、Mの暗号化は、

      C = P(M) = Mのp乗をNで割った余り

暗号文Cの復号は、

      M = S(C) = Cのs乗をNで割った余り

N,s,pの決定の仕方なんですが、まず3個の大きな素数を作ります。その中で最大のものをsとし、その他をx, yとします。Nはxとyの積とし、pを

                      psを(x - 1)(y - 1)で割った余りが1

となるように選びます。N、p、sがこのように選ばれているならば、すべてのメッセージM(ただし、0 =< M < N) に対して、

                    Mのps乗をNで割った余り   =   M

であることが証明されているようです。

暗号化してみよう

メッセージ : 「L DO YOU KNOW GODS OF DEATH LOVE APPLES」を暗号化したいと思います。「える しっているか しにがみはりんごしかたべない」を英訳したものです。デスノートで夜神ライトが犯罪者に文書を書かせて、横書きの文章の頭の文字をとってつなげると意味のある文章になるようにしてましたよね。こちらのサイトでこの文章の各国の翻訳が紹介されていました。

http://eruwaado.blog116.fc2.com/blog-entry-62.html

暗号化するために数値で計算しなければいけないので、下のように符号化します。

122704152725152127111415232707150419271506270405012008271215220527011616120519

Aはアルファベットの最初の英字だから01, Bは02... , Zは26というように対応させて符号化します。計算の規模を小さくするために、というより、計算の仕方がわからないので、100桁ではなく2桁の素数を例にとり、x=47, y=79, s=97とします。これから、N=3713, p=37が決まります。数字列の平文の暗号化は、4桁ずつ区切って整数とみなし、それを37乗したものを3713で割った余りを暗号文とします。暗号文は下のようになります。

08663334220810430519020800420795081424182904306614040477010714722561304426233706

1227を37乗して3713で割ったあまりは0866になるわけですね。復号する時は、p乗するところをs乗に変えればできます。ここで、メッセージを暗号化し、それを元の文に戻すプログラムを書いてみました。

なぜ素数なのか

復号鍵sは(Nの因数x, yとともに)秘密にされていますが、pとNを知っている暗号解析者がsをわかるとまずいですよね。さっきの小規模な例だと、3713=47×79であることがわかってしまうそうです。37×97 ≡ 1 (mod 46×78)であることもわかるそうです。僕はすぐにわかりませんが。Nが200桁の場合、その因数を見つけることは絶望的だそうです。現在の技術で最良の方法で計算しても、100万年以上かかるそうです。この暗号方式はSLL通信(ブラウザのurlバーの保護された通信ってやつ)などに利用されているそうです。素数も役に立つときがあるようですね。