RSA暗号

 今回はRSA暗号を実装したものになります。

　RSA暗号は素数の素因数分解困難性を安全性の根拠とする現代暗号で、開発者であるリベスト(Rivest)、シャミア(Shamir)、アドルマン(Adleman)からその名が付きました。今日でも用いられている公開鍵暗号化方式です。

　素数(prime number)は自身以外に約数を持たない自然数のことです。そのため、どのような素数pもp=1×pの形にしか分解できません。この素数を二つ用意しそれぞれp,qとし、その積をNとするとN=pqとおきます。このとき、pとqからNは簡単に求めることはできますが、Nからpとqを求めることはとても困難になります。中学数学で習う素因数分解ですが、実はインターネット上では重要な役割を担う技術の基礎になっているのです。

では暗号化の説明です。概略のみで数学的な証明については省略しますので気になる方は各自でお調べください。前述のとおりこの暗号では二つの素数p,qを用いて暗号化を行います。

まず、この二つの素数の積Nを求めます。

次に、以下の条件を満たす自然数eを選びます。gcdは最大公約数の意味です。以下の式では最大公約数が1であることから、互いに素であることを意味します。

さらに以下の条件を満たす自然数dを選びます。以下の式でdeと1は(p-1)*(q-1)を法として合同であり、ともに(p-1)(q-1)で割ると1余ることを意味しています。

以上の値を用いて、平文mの暗号化は以下の式で表されます。cは暗号文になります。

ただし、mには以下の制約があることに注意してください。

そして、暗号文cの復号は以下の数式であらわされます。

余談ですが「暗号化」の反対は「復号」であり、「復号化」とは言わないので注意が必要です。「暗号(名詞)」+「化」で「平文を暗号にする」という動詞にしているのに対し、「復号」は「元の平文に戻す」動作そのものを指すからです

以上がRSA暗号の一連の流れの概要になります。暗号を用いる際には(e,N)の組のみを公開し、dを秘匿しておきます。

では具体例でみていこうと思います。p=17,q=29,d=409,e=425を選択し、m=131を暗号化とします。すると、

というように暗号化・復号ができることになります。

では、プログラムの話になります。

今回は公開鍵と暗号文をTCP通信で送信し、受信側で復号を行うプログラムを作りました。動かすと次のような出力が出るようにしてあります。

送信側で次のようにデータを設定します。

受信側で次のように復号データを表示します。

e,dを乱数で選択できるような機能も実装していますが、その場合は送信の部分を書き換えてください。それほど難しくはないと思います。

ソースコードはこちらに置いておきます。引用明記の上、ご自由にお使いください。

紹介した数式の詳しい証明などについては以下の書籍などを参考にしてください。

参考

暗号理論入門　暗号アルゴリズム,署名と認証,その数学的基礎 原書第3版 J.A Buchman