ラビン暗号を実装してみる
こんにちは。ようやく暗号の話に入ることができます。今回はラビン暗号を取り上げます。
ラビン暗号とは
1979年にマイケル・ラビンさんによって発明された暗号で、合成数を素因数分解するのは難しいことに基づいた暗号です。マイケル・ラビンさんについて書かれたWikipediaのページのリンクを貼っておきます。
https://ja.wikipedia.org/wiki/マイケル・ラビンラビン暗号のアルゴリズム
鍵を生成するアルゴリズム
\(4k+3\)（\(k\)は整数\)の形をした２つの素数の組\((p,q)\)を見つけます。\((p,q)\)が見つかったら、\(N=pq\)を求めます。\(0 \leq b \leq N-1\)から整数\(b\)を選びます。ここまでで求めた\((N,b)\)の組が公開鍵、\((p,q)\)の組が秘密鍵になります。ここでは簡単のため\(b=0\)とします。
ここで、\(4k+3\)の形であっても必ずしも素数とならないことに注意が必要です。\(4\times 13 + 3 =55\)は、\(5\)の倍数になり素数ではありません。
また、素数だからといって\(4k+3\)の形になるわけでもありません。例えば、\(89\)は素数ですが\( 4 \times 22 +1\)となっています。
暗号化するアルゴリズム
次に平文を暗号化します。平文を\(m\)としたとき、暗号は次により求められます。
\[c = m(m+b) \bmod N \]
\(b=0\)とすることにより、\(c \equiv m^2 \bmod N\)により暗号化できます。
ここで注意が必要なのは、暗号化は単射ではありません。具体的には、\(p=7,q=11,N=77\)としたとき、平文\(m=2\)を暗号化すると暗号\(c=4\)となりますが、\(c=4\)になるものは\(m=2,9,68,75\)の４個存在します。\(68 \equiv -9 \bmod 77\)（\(77\)で割ると\(68\)余る数は、\(77\)で割ると\(9\)不足する）と考えると、\(m=\pm2,\pm9\)の４個存在します。
平文\(m\)に対して暗号化した\(c\)は一意に決まりますが、暗号文\(c\)に対して復号した\(m\)が一意に決まらないことに注意が必要です。。
復号するアルゴリズム
続いて復号のアルゴリズムです。\(b=0\)のとき、次の連立方程式の解\(x\)が復号された結果になります。
\[\begin{eqnarray} x_p &\equiv& c^{\frac{p+1}{4}}\bmod p \\ x_q &\equiv& c^{\frac{q+1}{4}}\bmod q \end{eqnarray}\]
としたときに、
\[x_1 \equiv x_p \bmod p かつ x_1 \equiv x_q \bmod q となるx_1\]
\[x_2 \equiv -x_p \bmod p かつ x_2 \equiv x_q \bmod q となるx_2\]
\[x_3 \equiv x_p \bmod p かつ x_3 \equiv -x_q \bmod q となるx_3\]
\[x_4 \equiv -x_p \bmod p かつ x_4 \equiv -x_q \bmod q となるx_4\]
を中国剰余の定理を用いて得られる\(x_1,x_2,x_3,x_4\)のいずれかが復号候補になります。復号候補から復号結果を特定するには、冗長な情報を持たせるなどの工夫が必要そうです。
上の例では、\(x_p \equiv 4^{\frac{7+1}{4}} \equiv 4^2 \equiv 16 \equiv 2\bmod 7\)、\(x_q \equiv 4^{\frac{11+1}{4}} \equiv 4^3 \equiv 64 \equiv 9\bmod 11\)より
\[x_1 \equiv 2 \bmod 7 かつ x_1 \equiv 9 \bmod 11 となるx_1 \equiv 9 \bmod 77\]
\[x_2 \equiv -2 \bmod 7 かつ x_2 \equiv 9 \bmod 11 となるx_2 \equiv 75 \bmod 77\]
\[x_3 \equiv 2 \bmod 7 かつ x_3 \equiv -9 \bmod 11 となるx_3 \equiv 2 \bmod 77\]
\[x_4 \equiv -2 \bmod 7 かつ x_4 \equiv -9 \bmod 11 となるx_4 \equiv 68 \bmod 77\]
のいずれかが復号結果の候補となります。
ラビン暗号を実装してみる
毎度のPythonで実装してみます。半角英数記号の文字コードを暗号化する前提で、復号結果が32以上127以下の範囲に収まることを復号結果の特定方法としました。（確実に復号できる保証は全くありませんが・・・）
import random
import sympy.ntheory.modular
def code( word ):
result = []
for letter in word:
result.append( ord(letter) )
return result
def is_prime( n ):
i = 3
while i*i<=n:
if n % i == 0:
return False
i += 2
return True
def make_prime( bit ):
while True:
k = random.randint( 1<<(bit-3), ( 1<<(bit-2)) -1 )
n = 4*k + 3
if is_prime( n ):
return n
def calc_mod( a, b, p ):
result = 1
for i in range(b):
result = ( result * a ) % p
return result
def power( a, e, p ):
result = 1
i = 1
while i <=e:
result = ( result * a ) % p
i += 1
return result
def key_generate( k ):
p = make_prime( k )
q = p
while p==q:
q = make_prime( k )
n = p * q
return n, ( p, q )
def encrypt( m, pk ):
cipher = []
n = pk
for l in m:
c = ( l*l ) % n
cipher.append( c )
return cipher
def decrypt( c, pk, sk ):
decode = ''
n = pk
p, q = sk
print( '平文コード 暗号mp mq m1 m2 m3 m4 m 復号' )
for i, cc in enumerate(c):
mp = power( cc, (p+1)/4, p )
mq = power( cc, (q+1)/4, q )
m1, N = sympy.ntheory.modular.crt( [ p, q ], [ mp, mq ] )
m2, N = sympy.ntheory.modular.crt( [ p, q ], [ -mp, mq ] )
m3, N = sympy.ntheory.modular.crt( [ p, q ], [ mp, -mq ] )
m4, N = sympy.ntheory.modular.crt( [ p, q ], [ -mp, -mq ] )
if 32<=m1 and m1 <=126:
m = m1
elif 32<=m2 and m2 <=126:
m = m2
elif 32<=m3 and m3 <=126:
m = m3
elif 32<=m4 and m4 <=126:
m = m4
decode += chr(m)
print('{0}\t{1:3}\t{2:5}\t{3:3}\t{4:3}\t{5:5}\t{6:5}\t{7:5}\t{8:5}\t{9:3}\t{10}'
.format( plain_text[i], plain_code[i], cc, mp, mq, m1, m2, m3, m4, m, decode[i] ) )
return decode
if __name__ == '__main__':
pk, sk = key_generate(7)
plain_text = ''
for i in range( 32, 127 ):
plain_text += chr(i)
plain_code = code( plain_text )
cipher = encrypt( plain_code, pk )
decode = decrypt( cipher, pk, sk )
decode_code = code( decode )
print( '公開鍵 ( N, b ) = ', pk )
print( '秘密鍵 ( p, q ) = ', sk )
print( '平文 = ', plain_text )
print( "復号 = ", decode )
実行結果です。乱数で２つの素数\(p,q\)を発生させており、素数の値の範囲を７ビット（６４以上１２８未満）にした場合には、復号結果が誤ることはなさそうでした。
平文コード 暗号mp mq m1 m2 m3 m4 m 復号
32 1024 32 32 32 2955 5182 8105 32
! 33 1089 33 46 1784 8104 33 6353 33 !
" 34 1156 34 45 6523 8103 34 1614 34 "
# 35 1225 68 44 8102 3125 5012 35 35 #
$ 36 1296 36 36 36 273 7864 8101 36 $
% 37 1369 66 42 8100 4466 3671 37 37 %
& 38 1444 38 38 38 7069 1068 8099 38 &
' 39 1521 64 40 8098 5807 2330 39 39 '
( 40 1600 63 40 5728 40 8097 2409 40 (
) 41 1681 41 38 7148 8096 41 989 41 )
* 42 1764 61 42 4387 42 8095 3750 42 *
+ 43 1849 60 36 8094 352 7785 43 43 +
, 44 1936 59 44 3046 44 8093 5091 44 ,
- 45 2025 58 45 6444 45 8092 1693 45 -
. 46 2116 46 46 46 1705 6432 8091 46 .
/ 47 2209 56 32 8090 3034 5103 47 47 /
0 48 2304 55 31 8089 7773 364 48 48 0
1 49 2401 49 49 49 3762 4375 8088 49 1
2 50 2500 50 50 50 7160 977 8087 50 2
3 51 2601 52 51 2421 51 8086 5716 51 3
4 52 2704 52 52 52 5819 2318 8085 52 4
5 53 2809 50 26 8084 7057 1080 53 53 5
6 54 2916 49 25 8083 3659 4478 54 54 6
7 55 3025 55 55 55 7876 261 8082 55 7
8 56 3136 56 23 5000 8081 56 3137 56 8
9 57 3249 46 22 8080 1602 6535 57 57 9
: 58 3364 58 21 6341 8079 58 1796 58 :
; 59 3481 59 20 2943 8078 59 5194 59 ;
< 60 3600 60 19 7682 8077 60 455 60 <
= 61 3721 61 18 4284 8076 61 3853 61 =
> 62 3844 41 62 7251 62 8075 886 62 >
? 63 3969 63 16 5625 8074 63 2512 63 ?
@ 64 4096 64 64 64 5910 2227 8073 64 @
A 65 4225 38 65 1171 65 8072 6966 65 A
B 66 4356 66 13 3568 8071 66 4569 66 B
C 67 4489 36 67 7967 67 8070 170 67 C
D 68 4624 68 11 4909 8069 68 3228 68 D
E 69 4761 34 10 8068 1511 6626 69 69 E
F 70 4900 33 9 8067 6250 1887 70 70 F
G 71 5041 32 8 8066 2852 5285 71 71 G
H 72 5184 72 72 72 546 7591 8065 72 H
I 73 5329 30 73 3944 73 8064 4193 73 I
J 74 5476 29 5 8063 795 7342 74 74 J
K 75 5625 28 4 8062 5534 2603 75 75 K
L 76 5776 76 76 76 6001 2136 8061 76 L
M 77 5929 26 2 8060 6875 1262 77 77 M
N 78 6084 25 1 8059 3477 4660 78 78 N
O 79 6241 79 0 79 8058 79 8058 79 O
P 80 6400 23 1 3319 80 8057 4818 80 P
Q 81 6561 81 2 81 6717 1420 8056 81 Q
R 82 6724 82 76 6159 8055 82 1978 82 R
S 83 6889 83 4 83 5376 2761 8054 83 S
T 84 7056 19 5 637 84 8053 7500 84 T
U 85 7225 18 73 8052 4102 4035 85 85 U
V 86 7396 17 72 8051 704 7433 86 86 V
W 87 7569 16 8 2694 87 8050 5443 87 W
X 88 7744 15 9 6092 88 8049 2045 88 X
Y 89 7921 14 10 1353 89 8048 6784 89 Y
Z 90 8100 13 11 4751 90 8047 3386 90 Z
[ 91 144 91 67 8125 8046 91 12 91 [
\ 92 327 92 13 92 3410 4727 8045 92 \
] 93 512 93 65 1329 8044 93 6808 93 ]
^ 94 699 9 64 8043 6068 2069 94 94 ^
_ 95 888 8 16 5467 95 8042 2670 95 _
` 96 1079 7 62 8041 7409 728 96 96 `
a 97 1272 97 18 97 4126 4011 8040 97 a
b 98 1467 98 19 98 7524 613 8039 98 b
c 99 1664 4 20 2785 99 8038 5352 99 c
d 100 1863 100 21 100 6183 1954 8037 100 d
e 101 2064 2 22 1444 101 8036 6693 101 e
f 102 2267 1 23 4842 102 8035 3295 102 f
g 103 2472 0 55 8034 8034 103 103 103 g
h 104 2679 1 25 104 3501 4636 8033 104 h
i 105 2888 2 26 105 6899 1238 8032 105 i
j 106 3099 100 52 8031 5977 2160 106 106 j
k 107 3312 4 51 2579 8030 107 5558 107 k
l 108 3527 98 50 8029 7318 819 108 108 l
m 109 3744 97 49 8028 3920 4217 109 109 m
n 110 3963 7 31 110 7615 522 8027 110 n
o 111 4184 8 32 111 2876 5261 8026 111 o
p 112 4407 9 46 1863 8025 112 6274 112 p
q 113 4632 93 45 8024 6602 1535 113 113 q
r 114 4859 92 44 8023 3204 4933 114 114 r
s 115 5088 91 36 194 115 8022 7943 115 s
t 116 5319 13 42 4545 8021 116 3592 116 t
u 117 5552 14 38 117 6990 1147 8020 117 u
v 118 5787 15 40 5886 8019 118 2251 118 v
w 119 6024 16 40 119 5649 2488 8018 119 w
x 120 6263 17 38 7227 8017 120 910 120 x
y 121 6504 18 42 121 4308 3829 8016 121 y
z 122 6747 19 36 431 8015 122 7706 122 z
{ 123 6992 83 44 2967 123 8014 5170 123 {
| 124 7239 82 45 6365 124 8013 1772 124 |
} 125 7488 81 46 1626 125 8012 6511 125 }
~ 126 7739 23 32 3113 8011 126 5024 126 ~
公開鍵 ( N, b ) = 8137
秘密鍵 ( p, q ) = (103, 79)
平文 = !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
復号 = !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
復号のアルゴリズムでの数学的な部分が消化不良ですが、今回はこれでおしまいにします。それではまた。