RSA暗号方式において、公開鍵から秘密鍵を推測してみた。

概要

セキュリティの勉強のため、pythonでRSA暗号方式を実装するとともに、公開鍵から秘密鍵を推測してみた。

RSA暗号方式の実装

wikipediaのRSA暗号の記事を見ながら、コードを書いた。

基本的には、nとe(公開鍵)で暗号化して、nとd(秘密鍵)で復号する。nとeは公開されるが、dは公開されない。nは二つの素数p,qを掛け合わせた数である。p,qは公開されない。

詳細なアルゴリズムは下記の暗号方式参照。
https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7

# coding: utf-8
# Here your code !
import base64

class SquareMatrix:
    def __init__(self, a11,a12,a21,a22):
        self.a11 = a11
        self.a12 = a12
        self.a21 = a21
        self.a22 = a22
    def __mul__(self,other):
        a11 = self.a11*other.a11 + self.a12*other.a21 
        a12 = self.a11*other.a12 + self.a12*other.a22
        a21 = self.a21*other.a11 + self.a22*other.a21
        a22 = self.a21*other.a12 + self.a22*other.a22
        return SquareMatrix(a11,a12,a21,a22)

def bezout(m,n):
    if m < n:
        n, m = m, n
    q, r = division(m,n)
    m, n = n, r
    sq1 = SquareMatrix(0,1,1,q*(-1))
    while r != 0:
        q, r = division(m,n)
        m, n = n, r
        sq1 = SquareMatrix(0,1,1,q*(-1)) * sq1
    return sq1.a11, sq1.a12

def division(m,n):
    if m < n:
        n, m = m, n
    return m//n, m%n

def phy(p,q): return (p-1)*(q-1)


def gcd(m,n):
    if m < n:
        n, m = m, n
    while n != 0:
        m, n = n, m%n  
    return m

def encrypt(message,n,e):
    ret = []
    for s in message:
        ret.append(str(ord(s)**e % n))
    return base64.b64encode(','.join(ret))

def get_remainder_after_power(x,y,z):
    ans = 1
    for i in range(y):
        ans *= x
        ans %= z
    return ans

def decrypt(message,n,d):
    ret = []
    for s in base64.b64decode(message).split(','):
        ret.append(chr(get_remainder_after_power(int(s), d, n)))
    return ''.join(ret)

def gen_keys(p,q):
    for e in range(p*q,1,-1):
        if e < phy(p,q) and gcd(phy(p,q),e) == 1:
            d1,d2 = bezout(e,phy(p,q))
            if d1 > 1 and d1*e % phy(p,q) == 1:
                return p*q,e,d1
            elif d2 > 1 and d2*e % phy(p,q) == 1:
                return p*q,e,d2

推測側アルゴリズム

nとe（公開鍵）とが与えられているという前提で秘密鍵dの推測を行う。
1. 素数pでnを割ることを繰り返すことにより、nを素因数分解し、他方の素数qを得る。
2. 得られたp,qを元に、暗号側アルゴリズムと同様の方式によりdを求める。
3. dが正数等、所定の条件を満たす場合に推測された秘密鍵として出力する。

import myprime
import myrsa

def attack(pmax, n, e):
    mp = myprime.MyPrime(pmax)
    for p in mp.prime_generator():
        q = n/p 
        if n%p == 0 and mp.is_prime(q):
            d1,d2 = myrsa.bezout(e,myrsa.phy(p,q))
            if d1 > 1 and (d1*e) % myrsa.phy(p,q) == 1:
                return d1
            elif d2 > 1 and (d2*e) % myrsa.phy(p,q) == 1:
                return d2

エラトステネスのふるいによって素数生成、素数判定を行うコード。

import math
class MyPrime:
    def __init__(self,pmax):
        self.prime_boolean = self.get_prime_boolean(pmax)
    def get_prime_boolean(self,pmax):
        boolean = [False,False]+[True]*(pmax-1)
        boolean[4::2] = [False] * (len(boolean[4::2]))
        p = 3
        square_of_pmax = int(math.sqrt(pmax))+1
        while p<=square_of_pmax:
            if boolean[p]:
                boolean[p**2::p] = [False] * (len(boolean[p**2::p]))
            p+=2
        return boolean

    def prime_generator(self):
        length = len(self.prime_boolean)
        return (i for i in range(2,length) if self.prime_boolean[i])

    def is_prime(self,number):
        return self.prime_boolean[number]

呼び出し側コード

対象の文(I love coding!)をRSA暗号方式により暗号文(encrypted_message)を生成する。推測側は、与えられた公開鍵n,eから推測されたdを求め、推測されたdにより暗号文を復号する。

# coding: utf-8
# Here your code !

import myrsa
import myrsaattacker

#p,q: prime numbers
#n: p*q
#e: key for encrypt. gcd(e,(p-1)(q-1)) == 1
#d: key for decrypt. e*d % ((p-1)(q-1)) == 1
#see https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7
#p, q = 13, 17
p,q = 23, 19
n, e, d = myrsa.gen_keys(p,q)

target_message='I love coding!' 
print "target_message: %s" % target_message
encrypted_message = myrsa.encrypt(target_message, n, e)
print "n:%s e:%s d:%s" % (n, e, d)
print "encrypted_message: %s" % encrypted_message
print "decrypted_message          : %s d:%s " % (myrsa.decrypt(encrypted_message,n,d),d)
pmax=1000
estimated_d = myrsaattacker.attack(pmax,n,e)
print "estimated_decrypted_message: %s estimated_d: %s " % (myrsa.decrypt(encrypted_message, n, estimated_d), estimated_d)

実行結果

復号に成功した。RSA暗号方式が、素因数分解と関連付けられていることを実感できた。

target_message: I love coding!
n:437 e:391 d:79
encrypted_message: MzQ3LDcyLDM5NSwzNjYsODUsMTE4LDcyLDE4MCwzNjYsMzYsMzc0LDIzOCwxOTgsNDA=
decrypted_message          : I love coding! d:79 
estimated_decrypted_message: I love coding! estimated_d: 79