こんにちは。ぽちゃまと申します。
この記事は[木更津高専 Advent Calendar] (https://qiita.com/advent-calendar/2019/nitkc) 2日目です。
前の記事：Verilog-HDLで32bit ALUを作った話
次の記事：数式の解釈を考える楽しみ
さて、僕は今高専4年生で課題研究のために研究室に配属されています。
その中でも、暗号(とセキュリティ)の研究室に配属になりました。
ということで、何か暗号を実装したいなと思い、考えた結果「RSA暗号」でした。
そして、理論を勉強した後に寝たらRSA暗号ができていました(??????????)。
ということで、寝てたらRSA暗号が生やすために、まずは理論を一緒に学んでいきましょう。
RSA暗号の実装(理論編)
RSAとは何か
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。
(参考：フリー百科事典『ウィキペディア（Wikipedia）』RSA暗号)
桁数が大きい合成数の素因数分解問題が困難であることというのはどういうことでしょうか？
例1)
2\times5 = 10
このような等式があったとします。
左辺が与えられた場合、掛け算をすれば右辺が簡単に求まります。、
逆に、右辺が与えられた場合も分解をすれば左辺が簡単に求まります。
では、次のパターンを見てみましょう。
例2)
23311 \times 27893 = 650213723
このような等式があったとします。
左辺から右辺を求めるのは頑張ればできそうです。
しかし、右辺から左辺を求めるのはとても困難です。
このように、大きな2素数の積を素因数分解をするのが困難であるということを利用してRSA暗号が作られました。
ただし、100桁以上同士の素数ならの話です。
##フェルマーの小定理
p が素数，a が任意の自然数のとき\\
（１）a^p \equiv a\pmod {p}\\
特に，a が p と互いに素な自然数のとき\\
（２）a^{p−1} \equiv 1\pmod {p}\\
証明は二項定理から数学的帰納法を用いる方法や、
整数の有名な定理
aとpが互いに素なとき，a,2a,3a,⋯(p−1)a をpで割った余りはすべて異なる
を用いる方法がある。
オイラーの定理
正整数 a,n に対して，a,n が互いに素であるとき，以下が成り立つ．\\
a\varphi(n)\equiv1\pmod n\\
ただし，\varphi(n) はオイラー関数を表す．
φ(m)のことをオイラー関数と言います。
オイラー関数は1からn-1までの自然数の中でnと互いに素なものの個数を表します。
また、これは先ほどのフェルマーの小定理を拡張したものです。
もし、nが素数pならば、オイラー関数はφ(p)=p-1より、a^(p-1)≡1(mod p)が成り立ちます。
参考:フリー百科事典『ウィキペディア（Wikipedia）オイラーの定理 (数論)
暗号方式
アリスとボブが通信をするときにどのように、暗号・復号化をするのか。
以下に手順を示します。
(A1)
アリスは異なる2つの巨大な素数p,qを求めます。
そして、
n = p\times q
を計算します。
(A2)
nに対するオイラー数
\varphi(n)=(p−1)(q−1)
を計算します。
(A3)
φ(n)以下で
(e,\varphi(n))= 1
なるような自然数eを求めます
すなわち、互いに素となる自然数eを求めるということです。
(A4)
φ(n)以下で
ed\equiv1\pmod {\varphi(n)}
を満たす自然数dを探します。
(ユークリッドの互除法を用いる)
(A5)
p, q, ϕ(n), d を秘匿して、n と e のみを公開します。
{p,q,φ(n),d}を秘密鍵、{n,e}を公開鍵といいます。
それでは、ボブがアリスに暗号を用いて通信をするにはどうすればよいかを以下に示します。
(B1)
ボブはアリスの公開鍵{n,e}を見つけます。
(B2)
ボブはアリスに送りたい平文をMとし、暗号文をCとします。
ボブは
C=P^e\pmod n
を計算します。
暗号文Cを受信したアリスは復号文Dを
D = C^d \pmod n
として計算します。
ここで、以下の定理を用います。
n を平方自由な（任意の素数の 2 以上のベキを因数としない）整数とする。\\
d と e を正の整数とし、de − 1 は n のすべての素因数 p に対して、p − 1 の倍数
であるとする\\（例えば、de \equiv 1 \pmod {\varphi(n)} ）。\\このとき、任意の整数 a について、
a^{de} \equiv a \pmod n が成り立つ。
よって、
D \equiv C^d \equiv (P^e)^d \equiv p^{de} \equiv P
となり、D=Pが成り立つので、暗号・復号化ができています。
参考:情報数理：暗号理論入門
参考に最後に用いた定理の証明が乗っています(定理1.7の系1.4)ので、興味のある方は見てみて下さい。
ここでは省略します。
#RSA暗号の実装(プログラム編)
今回、以下のサイトを参考にしました。
参考:RSA暗号方式をC言語で実装
##コード
#include <iostream>
#include <random>
#include <vector>
#define us unsigned
#define ui unsigned int
using namespace std;
ui prime(){
random_device random;
vector<us> primeNumber;
int number,i,flag = 0;
while(flag == 0) {
number = random() % 150;
for(i = 2; i <= sqrt(number); i++) {
if(number % i == 0) {
flag = 0;
break;
}
flag = 1;
}
}
return number;
}
ui gcd(ui a, ui b){
ui r = a%b;
while(r > 0){
a = b;
b = r;
r = a%b;
}
return b;
}
ui lcm(ui a, ui b){
return (a*b)/gcd(a, b);
}
ui extgcd(ui a, ui b){
int x1 = 1, y1 = 1, r1 = b;
int x2 = 0, y2 = 0, r2 = a;
int d;
while(true){
int q = r1/r2;
int r = r1%r2;
int x = x1-x2*q;
int y = y1-y2*q;
if(r == 0){
d = x2;
break;
}
x1 = x2;
y1 = y2;
r1 = r2;
x2 = x;
y2 = y;
r2 = r;
}
while(d <= 0){
d += b;
}
return d;
}
ui pow(ui M, ui e, ui n){
M %= n;
if(M == 0 || n == 0){
return 0;
}
if(e == 0){
return 1 % n;
}
ui val = 1;
for(int i = 0;i < e;i++){
val *= M;
if(val >= n){
val %= n;
}
}
return val;
}
int main(){
us p,q;
do{
p = prime();
q = prime();
}while(p == q);
if(p < q){
int tmp = p;
p = q;
q = tmp;
}
cout << "P: " << p <<" Q: " << q << endl;
us n = p*q;
us l = lcm(p-1,q-1);
us e = 2;
while(gcd(l, e) != 1){
e++;
}
us d = 2;
while((e*d)%l != 1){
d++;
}
cout << "N: " << n << " L: " << l << " E: " << e << " D: " << d << endl;
ui M;
cin >> M;
cout << "M: " << M << endl;
ui C = pow(M, e, n);
cout << "C: " << C << endl;
M = pow(C, d, n);
cout << "M: " << M << endl;
return 0;
}
prime関数
素数を生成してます。
gcd関数
ユークリッドの互除法を用いています。
このアルゴリズムを用いると、大きな数字の最大公約数を素早く求めることができます。
lcm関数
最小公倍数を求めています。
extgcd関数
拡張ユークリッドの互除法を用いています。
拡張ユークリッドの互除法では、
一次不定式
ax+by=c
の整数解を求めるアルゴリズムとなっています。
##pow関数
繰り返し自乗法を用いて、
a:底\\
k:指数\\
n:法
と定義するとき、法nのべき乗計算を求めることができます。
./a.out
P: 89 Q: 13 N: 1157 L: 264 E: 5 D: 53 1000
M: 1000
C: 870
M: 1000
./a.out
P: 83 Q: 37 N: 3071 L: 1476 E: 5 D: 1181 42000
M: 42000
C: 1941
M: 2077
平文(ここではM)がNより大きくなると、復号化失敗してしまいます。
今回は数字だけですが、条件を守っていればしっかりと暗号・復号化できているのがわかります。
最後に
文字の暗号・復号化する場合は一度数字に変換してからやればできると思いますが、時間が無くてまだできていないです。
できたら、ここに追記する(と思います)。
今回の記事で少しでも暗号に興味を持ってくれたらなと思います。
質問などがありましたら、Twitterに連絡をお願いします。
それでは！