C++でRSA暗号を実装する – 暗号化から復号までのプログラム

スポンサーリンク

 

こんにちは!HELLO!您好!привет там ! 안녕하세요 !Hola !

映画「サマーウォーズ」でお馴染みの RSA暗号。

最近 RSA暗号方式の基礎を学んだので、その感覚が鈍らないうちにチラ裏。

RSA暗号方式の概要をザっとをまとめてみました。

 

また、時間があったのでRSA暗号に用いる鍵ペアを生成するプログラムを書きました。

加えて、暗号化と復号を行うプログラムも書いて実際の流れをシミュレーションします。

 

基本的に殴り書きのメモとなっていますので、証明は割愛されています。

分かりにくい部分や誤りを含む部分もあるかと思いますがご了承ください。

 

時間がない人向けの粗削りとなっております。

要点チェックにお使い下さい。

 

RSA暗号の基礎

RSA暗号とは?

RSA暗号は公開鍵暗号方式の代表的なアルゴリズムの1つです。

公開鍵暗号は非対称鍵暗号とも呼ばれ、送信者と受信者は互いに異なる鍵を使用します。

秘密鍵と公開鍵の鍵ペアは受信者が用意します。

送信者は受信者の公開鍵を使いメッセージの暗号化を行い、受信者は秘密鍵を使ってメッセージを復号します。

 

RSA暗号の数学的基礎

RSA暗号は以下の数学的性質、とりわけ mod演算の性質に基づき成り立っています。

異なる大きな素数 \( p \) と\( q \) と任意の整数 Xに対して

$$ X^{LCM( p-1, q-1 )} \ mod \ pq = 1 $$

が常に成り立つ。

ただし、\( LCM( a, b ) \) は \(a\) と \(b\) の最小公倍数を表す。

 

鍵ペアの生成

 

受信者が用意する公開鍵と秘密鍵の鍵ペアは以下の手順により生成します。

  1.  異なる2つの大きな素数 \(p\) と \(q\) を用意
  2.  \(p\) と \(q\) の積 \( n \) (公開鍵) を用意
  3.  \(p\) \(-\) \(1\) と \(q\) \(-\) \(1\) の最小公倍数 \( m \) を用意
  4.  \(m\) との最大公約数が\(1\)である任意の整数 \(e\) (公開鍵) を用意
  5.  \( e \cdot d \mod m = 1 \) を満たす整数 \(d\) (秘密鍵) を用意

\(m\) と \(e\) はユーグリッド互除法を、\(d\) は拡張ユーグリッド互除法を用いて求めます。

 

ここでユーグリッド互除法と拡張ユーグリッド互除法について触れておきます。

 

ユーグリッド互除法 GCDとLCM

最大公約数を求める方法がユーグリッド互除法です。

正の整数 \(a\) と \(b\) ( \(a\) > \(b\) ) の最大公約数を \( GCD( a, b ) \) とすると

$$ GCD( a, b ) = GCD( b, a \ mod \ b ) $$

が成り立つ。

 

上記の性質を利用して2数の最大公約数を求めます。

 

次に最小公倍数の求め方ですが、以下の性質を利用します。

正の整数 \(a\), \(b\) の最大公約数を \(G\), 最小公倍数を \(L\) とすると

$$ ab = GL $$

が成り立つ。

 

以上の2つの性質を利用して最大公約数と最小公倍数を求めます。

プログラムを書く際も上記の性質を利用します。

 

拡張ユーグリッド互除法

整数 \(a\), \(b\) に対し、

$$ ax + by = GCD( a, b ) $$

を満たす整数 \(x\), \(y\) を求める方法が拡張ユーグリッド互除法です。

 

RSA暗号の秘密鍵 \(d\) は

$$ e \cdot d \ mod \ m = 1 $$

を満たす整数であることは確認しました。

このとき、上式を満たすことは

$$ ex + my = 1 $$

を満たすことと同値であるため、\(x\) が秘密鍵 \(d\) であることが分かります。

したがって、

$$ ax + by = 1$$

を満たす \(x\) を求める拡張ユーグリッド互除法の解法を考えればよいことになります。

 

例題を通して解法の手順を確認します。

 

例題

次の等式を満たす整数 \(x\), \(y\) を1組求めよ。

$$ 7x + 60y = 1 $$

\(a = 7\), \(b = 60 \) として以下の連立方程式をたてる。

\begin{cases}
0 \cdot a + 1 \cdot b &= b \ \\
1 \cdot a + 0 \cdot b &= a \ \
\end{cases}

まず、両式の右辺に初期値を代入する。

\begin{cases}
0 \cdot a + 1 \cdot b &= 60 \ \cdots(1) \ \\
1 \cdot a + 0 \cdot b &= 7 \ \cdots(2) \
\end{cases}

このとき \( 60 = 7 \times 8 + 4 \) より

$$ GCD( 60, 7 ) = GCD( 7,4 ) $$

\( (1) \ – (2) \times 8 = 4 \) であることから \( (3) \) 式を得る。

\begin{cases}
1 \cdot a + 0 \cdot b &= 7 \ \cdots(2) \ \\
-8 \cdot a + 1 \cdot b &= 4 \ \cdots(3) \
\end{cases}

同様にして \( 7 = 4 \times 1 + 3 \) より

$$ GCD( 7, 4 ) = GCD( 4,3 ) $$

\( (2) \ – (3) \times 1 = 3\) であることから \( (4) \) 式を得る。

\begin{cases}
-8 \cdot a + 1 \cdot b &= 4 \ \cdots(3) \ \\
\ 9 \cdot a \quad – 1 \cdot b &= 3 \ \cdots(4) \
\end{cases}

\( 4 = 3 \times 1 + 1 \) より

$$ GCD( 4,3 ) = GCD( 3,1 ) $$

\( (3) \ – (4) \times 1 = 1\) であることから \( (5) \) 式を得る。

\begin{cases}
\quad 9 \cdot a \quad – 1 \cdot b &= 3 \ \cdots(4) \ \\
-17 \cdot a \quad + 2 \cdot b &= 1 \ \cdots(5) \
\end{cases}

このとき \((5)\) 式に注目して

$$ a \cdot (-17) + b \cdot 2 = 1 $$

より、求める \( (x, y) \) の組み合わせの1つが \( (-17,2) \) であることが分かる。

 

 

以上が拡張ユーグリッド互除法の解法手順になります。

ただし RSA暗号の秘密鍵 \(d\) の場合、正の整数であることが好ましいため調整をします。

$$ ax + by = 1 \quad \Longleftrightarrow \quad a \cdot ( x + b ) + b \cdot ( y \ – a ) = 1 $$

の同値変形を利用し、\(x\) に適当回数 \(b\) を足すことで \(x\) の値を正にすることができます。

 

今回の場合は \( a \cdot ( -17 + 60 ) + b \cdot ( 2 \ – 7 ) = 1 \) より

$$ a \cdot 43 + b \cdot ( -5 ) = 1 $$

となります。

 

さて、それでは以上の前提知識を活用して RSA暗号を実装していきます。

RSA暗号の実装

プログラムの仕様

実際のRSA暗号のスケールを大幅に縮小した学習用のデモプログラムを実装します。

当プログラムでは始めに用意する2つの素数の桁数を4桁以下に限定し、乱数により決定します。

決定した2つの異なる素数をもとに暗号に必要な数値を全て自動的に計算し最後に端末に出力します。

ただし、公開鍵の1つである \(e\) の値は複数通り考えられる値のなかの最小値を取るように実装しました。

ソースコード

実行例 1実行例 2実行例 3実行例 4実行例 5



暗号化と復号

送信側

送信者は公開鍵 \(e\) と \(n\) を用いてメッセージを暗号化します。

送信するメッセージを \(M\)、暗号化されたメッセージを \(C\) とすると

$$ M ^{e} \ mod \ n \rightarrow C $$

の計算によりメッセージを暗号化した \(C\) を得ることができます。

送信者はこの \(C\) を相手に送ります。

受信側

受信者は秘密鍵 \(d\) と公開鍵 \(n\) を用いて送られてきたメッセージ \(C\) を復号します。

$$ C ^{d} \ mod \ n \rightarrow M $$

の計算によりメッセージを復号し、\(M\) を得ることができます。

 

冪剰余計算

上記の暗号化・復号の計算を行うプログラムを作成します。

単純にべき乗計算をしてから mod演算を試みるとオーバーフローになるため乗算の途中で剰余を適宜とります。

詳しいアルゴリズムは Wikipedia に掲載されていますので参考にしてください。

 

また暗号化と復号は同様の計算を行っているため同一のプログラムを使用しても構いませんが、

今回は2つのプログラムを作成して明確に分けました。

送信者の計算処理は encryption.cpp に、受信者の処理は decryption.cpp に記述します。

ソースコード

encryption.cpp

 

decryption.cpp

 

RSA暗号のシミュレーション

 

最後に、作成した3つのプログラムを使って RSA暗号の一連の処理の流れをシミュレーションします。

  1. rsaプログラムで公開鍵と秘密鍵を取得
  2. encryptionプログラムで任意の整数値を暗号化
  3. decryptionプログラムで暗号化した数値を復号

以下プログラム実行結果です。

rsaencryptiondecryption

 

rsaencryptiondecryption

 

rsaencryptiondecryption

 

rsaencryptiondecryption

 

失敗例です。

rsaencryptiondecryption

値によりますが、8桁のメッセージから復号結果が送信メッセージと一致しなくなりました。

成功する場合もありますが、成功率は低く動作は不安定です。

環境にもよると思われますが、当プログラムの送信メッセージの限界桁数は 7桁であることが判明しました。

 

考察と感想

 

公開鍵と秘密鍵とを取得するRSA暗号プログラムは与えられたアルゴリズムを単純に実装することで比較的簡単に実装できることが分かりました。

ただし、問題は取得した鍵ペアを利用してメッセージを暗号化・復号する計算プログラムであり、

桁あふれをいかに回避しながら効率よく計算するかです。

今回のプログラム作成を通して僕は初めてオーバーフローと真剣に向き合った気がします。

 

またこれは注意事項でもあるのですが、当プログラムは実行環境により動作が不安定になります。

豊富な資源をもつ大学の計算機でまわす場合は安定して暗号化・復号を行っていましたが、

自分のノートパソコンで実行する場合はすぐにオーバーフローにより正確な復号ができません。

送信メッセージが 5桁を越える程度で復号結果が送信メッセージと一致しなくなります。

 

もしかしたらオーバーフローではなく僕のプログラムに何らかの誤りがあるからかもしれませんが。

 

いづれにせよ、やはり自分の知識や技術力がまだまだ備わっていないことを痛感しました。

頑張ります!

 

ということで RSA3分クッキングはこれにて。

ちなみにこの記事のトップ画像の絵は暗号文字で「RSAencryption」の意。

ではまた!

スポンサーリンク


ABOUT ME

yuk!

国立大学情報学科に通う大学生です。天然パーマと戦いながらすーぱーエンジニアを目指し技術とセンスを磨いています。 室内に引きこもりがちでヘビメタと猫と甘いものが救いのキーボードカチャカチャ生活ですが、最近はブログで文章を書くことが楽しいです。モットーは「 Who dares wins. = 人生是一箇,活殺全在我。」好きな言葉は「マジ卍」。