¾ðÊó´ðÁÃ/¥³¥ó¥Ô¥å¡¼

情報基礎/コンピュータ数学
暗号への応用 1
情報基礎/コンピュータ数学
1 / 17
1
暗号への応用
シーザー暗号
アフィン暗号
2
練習問題
情報基礎/コンピュータ数学
2 / 17
暗号の用語
送信者：メッセージを送信する人
受信者：メッセージを受信する人
平文：暗号化される前の文
暗号文：暗号化された後の文
復号化：暗号文を平文に戻すこと
暗号鍵：暗号化にもちいる鍵
復号鍵：復号化にもちいる鍵
共通鍵暗号：暗号化と復号化に用いる鍵が同じ暗号
公開鍵暗号：暗号化と復号化に用いる鍵が異なる暗号
This is a pen → 01101010101（暗号化）
This is a pen ← 01101010101（復号化）
情報基礎/コンピュータ数学
3 / 17
シーザー暗号
シーザー暗号
各アルファベットを辞書順に k 文字シフトしたものをシーザー暗号とい
う．これは共通鍵暗号である．
【例】アルファベット {A, B, ·, Z} からなる平文を考える．k = 1 のとき
のシーザー暗号は以下のようになる．
A → B, B → C, · · · , Y → Z, Z → A
つまり，THIS IS A PEN は UIJT JT B QFM と暗号化される．復号化は
逆の操作を行えばよい．
情報基礎/コンピュータ数学
4 / 17
シーザー暗号のプログラム
大文字アルファベットを 1 つ受け取って暗号化した文字を出力する．復
号化は自分たちで考える．
#include<iostream>
using namespace std;
int main(void){
char c;
cin >> c;
cout << (char)((c-’A’+k)%26+’A’) << endl;
return 0;
}
情報基礎/コンピュータ数学
5 / 17
文字を数字に割り当てる
簡単のためアルファベットの大文字 26 文字のみを扱う．アルファベット
を以下のように数字に対応させる．
A
0
B
1
C
2
···
···
Y
24
Z
25
つまり，各文字が Z26 の要素に対応している．
【例】APPLE に対応する数字列は (0, 15, 15, 11, 4) となる．
問 7.1
上の文字コードで，SEIKEI はどのような数字列になるか．
情報基礎/コンピュータ数学
6 / 17
逆元
定義 7.1
m を任意の自然数，a を gcd(m, a) = 1 である任意の自然数とする．
a′ · a ≡m 1 を満たす，a′ ∈ Zm を，
（m を法とした）a の逆元といい，a−1
と表記する．
命題 7.1
m を任意の自然数，a を gcd(m, a) = 1 である任意の自然数とする．
a′ · a ≡m 1 を満たす，a′ ∈ Zm が一意に存在する．
情報基礎/コンピュータ数学
7 / 17
逆元の存在性
【証明】定理 6.18 より，ある整数 s と t が存在して，
gcd(m, a) = sm + ta
gcd(m, a) = 1 より，sm + ta = 1．よって，
ta ≡m 1 − sm ≡m 1
もし t が Zm の要素であれば，a′ = t とすれば命題が示される．そうでな
い場合，t + km ∈ Z26 となる k を用いて，a′ = t + km とすれば，
a′ a = (t + km)a = ta + kma ≡m ta ≡m 1
となり，命題が示される．
情報基礎/コンピュータ数学
8 / 17
逆元の求め方
問 7.2
m = 30 を法とした a = 13 の逆元を求めよ．
【解答】ベズーの等式を用いる．ユークリッドの互除法より，
30 = 2 · 13 + 4
13 = 3 · 4 + 1
なので，
1 = 13 − 3 · 4
= 13 − 3 · (30 − 2 · 13)
= −3 · 30 + 7 · 13
これより，
1 ≡30 7 · 13
となるので，a = 13 の逆元は a−1 = 7 である．
情報基礎/コンピュータ数学
9 / 17
逆元の求め方
問 7.2
m = 13 を法とした a = 30 の逆元を求めよ．
【解答】ベズーの等式を用いる．ユークリッドの互除法より，
30 = 2 · 13 + 4
13 = 3 · 4 + 1
なので，
1 = 13 − 3 · 4
= 13 − 3 · (30 − 2 · 13)
= −3 · 30 + 7 · 13
これより，
1 ≡13 (−3) · 30
となるので，a = 30 の逆元は a−1 = (−3) + 13 = 10 である．
情報基礎/コンピュータ数学
10 / 17
アフィン暗号
アフィン暗号
m = 26 とする．a ∈ N を gcd(m, a) = 1 である任意の自然数として，a−1
を a の逆元とする．また，b を任意の自然数とする．このとき，アフィン
暗号の暗号化関数 E : Zm → Zm は，任意の x ∈ Zm に対して，
E(x) = ax + b
mod m
となる．また復号化関数 D : Zm → Zm は，任意の y ∈ Zm に対して，
D(y) = a−1 (y − b)
mod m
となる．このとき，(a, b) が暗号鍵，(a−1 , −b) が復号鍵となる．
情報基礎/コンピュータ数学
11 / 17
アフィン暗号
【例】(a, b) = (25, 1) とするとき，アフィン暗号化関数は
E(x) = 25x + 1 mod 26 となるので，以下の計算より，ABC のアフィ
ン暗号文は BAZ となる．
A : E(0) = 25 · 0 + 1 ≡26 1
B : E(1) = 25 · 1 + 1 ≡26 0
C : E(2) = 25 · 2 + 1 ≡26 25
また逆元を求めると a−1 = 25 となるため，アフィン復号化関数は
D(y) = 25(y − 1) mod 26 となるので，以下の計算より，暗号文 BAZ
は確かに ABC に復号される．
B : D(1) = 25 · (1 − 1) ≡26 0
A : D(0) = 25 · (0 − 1) ≡26 1
Z : D(25) = 25 · (25 − 1) ≡26 2
情報基礎/コンピュータ数学
12 / 17
アフィン暗号
問 7.3
自然数 (a, b) = (25, 1) として，アフィン暗号を用いた場合，SEIKEI の暗
号文は何か．
問
問 7.3 においてアフィン暗号の復号化関数を求め，暗号文が正しく
SEIKEI に復号されることを確認せよ．
情報基礎/コンピュータ数学
13 / 17
アフィン暗号の正当性
命題 7.2
任意の x ∈ Zm について，
D(E(x)) = x
【証明】関数 E ，D を合成すると，
D(E(x)) = a−1 (((ax + b) mod m) − b)) mod m
より，
D(E(x)) ≡m a−1 ((ax + b) mod m) − b)
ここで，ax + b mod m はある q を用いて，
ax + b mod m = ax + b − mq
と表せる．
情報基礎/コンピュータ数学
14 / 17
アフィン暗号の正当性
【証明の続き】よって，
D(E(x)) ≡m a−1 ((ax + b − mq) − b)
≡m a−1 (ax − mq)
≡m a−1 · ax − a−1 · mq
今，a−1 · mq ≡m 0 なので，
D(E(x)) ≡m a−1 · ax
また，a−1 · a ≡m 1 より，
D(E(x)) ≡m x
情報基礎/コンピュータ数学
15 / 17
練習問題
練習問題 1
各 m，a について，法 m における a の逆元 a−1 を求めよ．
(1) m = 29，a = 12
(2) m = 26，a = 7
(3) m = 22，a = 5
(4) m = 13，a = 31
(5) m = 17，a = 21
(6) m = 9，a = 29
情報基礎/コンピュータ数学
16 / 17
練習問題
練習問題 2
アフィン暗号において，次の暗号化関数 E(x) をもちいて SEIKEI の暗号
文を求めよ．また復号化関数 D(y) を求め，暗号文から SEIKEI に復号で
きることを確かめよ．
(1) E(x) = 5x + 3 mod 26
(2) E(x) = 7x + 5 mod 26
(3) E(x) = 11x + 2 mod 26
(4) E(x) = 9x + 4 mod 26
情報基礎/コンピュータ数学
17 / 17

Download Report