RSAの暗号方式を調べた

公開鍵暗号方式に使われるRSA暗号方式は、Rivest(ライベスト),Shamir(シャミール),Adleman(エイドルマン)の3人によって1977年に考案された。3人の頭文字を取り、RSAと名付けられた。Rivestはハッシュ関数MD5の作者でもある。

 

RSAの暗号方式を理解すると、

公開鍵で暗号化したデータは秘密鍵で復号でき、

秘密鍵で暗号化したデータが公開鍵で復号できる、

ということが分かる。

 

RSA暗号化には、2つの素数p,qと、2つの1以上の任意の整数e,nを用いる

復号化に使う整数dは以下の式で求められる。

d = ( n(p-1)(q-1) + 1 ) / e

暗号化と復号化は以下の式で求められる。

暗号化: 平文^e       mod   p*q   =   暗号文

復号化: 暗号文^d   mod   p*q   =   平文

実際にはpとqは、それぞれ100桁以上の2つの素数を用いて暗号化と復号化を行うが、

例として、以下の数字で暗号化と復号化を行ってみる

p = 3

q = 11

e = 7

n = 1

d = 3 dは( 1(3-1)(11-1) + 1) / 7より求められる

平文を9とすると、

暗号化: 9^7       mod   3*11   =   15

復号化: 15^3   mod   3*11   =   9

となる。

 

他の暗号方式も調べてみた。

AES(Advanced Encryption Standard):アメリカの暗号規格。共通鍵暗号方式に使われる。1997年に、一般公募の中から、ベルギーの研究者が開発したラインダール暗号方式が採用された。実際にはAESの公募ルールに合わせて、機能の制限をされたものが、AESとして使われている。暗号化の方法はDESのやり方と似ているっぽいけど、よくわからなかった。

旧規格 DES (FIPS 46) の安全性が低下したため、1997年9月にNIST(アメリカ国立標準技術研究所)が後継の暗号標準AES (Advanced Encryption Standard) とすべく共通鍵ブロック暗号を公募した。

*1

 

DES(Data Encryption Standard):1977年に正式に発表されてから、ラインダール(Rijndael) がAESに採用される2000年まで使われていた旧暗号方式。56 bit の鍵を使う。暗号化は以下の通り。

f:id:bambinya:20150311232732g:plain