お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

ラビン暗号を実装してみる

情報セキュリティ

こんにちは。ようやく暗号の話に入ることができます。今回はラビン暗号を取り上げます。

ラビン暗号とは

1979年にマイケル・ラビンさんによって発明された暗号で、合成数を素因数分解するのは難しいことに基づいた暗号です。マイケル・ラビンさんについて書かれたWikipediaのページのリンクを貼っておきます。

ラビン暗号のアルゴリズム

鍵を生成するアルゴリズム

\(4k+3\)(\(k\)は整数\)の形をした2つの素数の組\((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\)の4個存在します。\(68 \equiv -9 \bmod 77\)(\(77\)で割ると\(68\)余る数は、\(77\)で割ると\(9\)不足する)と考えると、\(m=\pm2,\pm9\)の4個存在します。

平文\(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 )

実行結果です。乱数で2つの素数\(p,q\)を発生させており、素数の値の範囲を7ビット(64以上128未満)にした場合には、復号結果が誤ることはなさそうでした。

平文コード 暗号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{|}~

復号のアルゴリズムでの数学的な部分が消化不良ですが、今回はこれでおしまいにします。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai