Python RSA 키 생성 - Python RSA ki saengseong

rsa 는 두 소수의 곱으로 이루어진 어떤 수 n를 소인수분해하는 문제가 어렵다는 점을 이용한다.

따라서 n 이 충분히 큰 수여야하고, n 을 두 소수로 소인수분해할 수 있으면 암호가 깨진다.

main 함수

키 쌍을 생성한 후, 암호화 복호화가 잘 이루어지는지 확인한다.

"""
RSA test
"""
if __name__ == "__main__":
    e, d, n = keygen(512)  # 512-bits 키 생성
    M = 88  # 평문
    C = encrypt(M, e, n)  # 암호문
    MM = decrypt(C, d, n)  # 복호화한 평문
    if M == MM:
        print("Example of RSA Algorithm works successfully")
        print("M={}, PU=({},{}), PR=({},{}), C={}, MM={}".format(M, e, n, d, n, C, MM))
    else:
        print("Example of RSA Algorithm works fail")
        print("M={}, PU=({},{}), PR=({},{}), C={}, MM={}".format(M, e, n, d, n, C, MM))

키 생성 코드

1. 충분히 큰 소수 p, q를 생성 (miller rabin 테스트)
2. n = p * q
3. \(\phi(n)= (p-1) * (q-1)\) 를 만족하는 \(mod \ \phi(n)\) 연산에 대하여, 곱셈역원 관계인 임의의 e 와 d를 생성
4. (e, n) 이 private key, (d, n)이 public key로 사용

"""
RSA key pair generation
keylen: security parameter (desired number of bits in n)
    (keylen > 4)
"""
def keygen(keylen):
    bound = 1 << keylen//2   # upper bound for p and q.
    p = 2 * random.randint(bound//4, bound//2) - 1       # guarantee that p is odd.
    while miller_rabin(p, 50) == Composite:
        p = 2 * random.randint(bound//4, bound//2) - 1   # select new odd p.
    q = 2 * random.randint(bound//4, bound//2) - 1       # guarantee that q is odd.
    while miller_rabin(q, 50) == Composite:
        q = 2 * random.randint(bound//4, bound//2) - 1   # select new odd q.
    # Now p and q are odd primes.

    n = p * q
    phi_n = (p-1) * (q-1)  # euler totient function phi(n)
    
    # find e, satisfing gcd(phi(n), e) == 1, where 1 < e < phi(n)
    while gcd(phi_n, (e := random.randint(1, phi_n))) != 1:
        pass
    d = m_inv(e, phi_n)  # multiplicative inverse of Modular phi(n)

    return (e, d, n)

더보기

"""
miller-rabin prime test
Test if n is prime with error probability less than 2^n.
"""
Prime = 0
Composite = 1
def miller_rabin(n, s):
    if n == 2:
        return Prime
    elif n % 2 == 0:
        return Composite

    for _ in range(s):
        a = random.randint(1, n-1)
        if test(a, n) == True:
            return Composite

    return Prime

"""
subroutine for miller-rabin prime test
Perform the Fermat test and NSR (nontrivial square root) test.
"""
def test(a, n):
    bits = int_to_bin(n-1)
    k = len(bits) - 1
    t = 0

    while bits[k] == '0':
        t += 1
        k -= 1

    u = (n-1) >> t
    x = exp(a, u, n)
    for _ in range(t):
        _x = x
        x = (_x * _x) % n
        if x == 1 and _x != 1 and _x != n-1:
            return True

    if x != 1:
        return True
    else:
        return False

더보기

"""
GCD(assume a>=0, b>=0, a>=b )
"""
def gcd(a, b):
    if a < b:
        a, b = b, a
    if a == b:
        return a
    elif b == 0:
        return a
    else:
        return gcd(b, a % b)

더보기

"""
Multiplicative Inverse

x = a^-1 mod n
a * x mod n = 1

"""
def m_inv(a, n):
    x, y, r = extended_euclid(n, a % n)
    if r != 1:
        print("No multiplicative inverse")
        return
    else:
        return y % n
        
"""
Extended Euclidean Algorithm (Iterative version) ( a >= b )

return (x, y, r) such that a * x + b * y = r = gcd(a, b)
loop invariant :
a * x_1 + b * y_1 = r_1
a * x_2 + b * y_2 = r_2

"""
def extended_euclid(a, b):

    if a == b:
        return 1, 0, a
    elif b == 0:
        return 1, 0, a
    else:
        x_1 = 1
        y_1 = 0
        r_1 = a

        x_2 = 0
        y_2 = 1
        r_2 = b

        while r_2 != 0:
            q = r_1 // r_2

            r_t = r_1 - q * r_2
            x_t = x_1 - q * x_2
            y_t = y_1 - q * y_2

            x_1, y_1, r_1 = x_2, y_2, r_2
            x_2, y_2, r_2 = x_t, y_t, r_t

        return x_1, y_1, r_1

암복호화 코드

"""
RSA encryption
e, n: public key
M: plaintext < n
"""
def encrypt(M, e, n):
    return exp(M, e, n)

"""
RSA decryption
d, n: private key
C: ciphertext < n
"""
def decrypt(C, d, n):
    return exp(C, d, n)
    
"""
Modular exponentiation
returns a ^ b mod n
Time complexity is O(logb)
"""
def exp(a, b, n):
    c = 0
    f = 1
    bin_b = int_to_bin(b)
    k = len(bin_b)
    for i in range(k):   
        c = 2*c
        f = f*f % n
        if bin_b[i] == '1':
            c = c+1
            f = f*a % n
    return f

더보기

"""
int_to_bin
convert an integer to a binary representation
(the most significant bit becomes the 0-th bit)
"""
def int_to_bin(num):
    return list(bin(num))[2:]  # eliminate first two, ex) 0b00101001

전체코드

더보기

import random
import sys
sys.setrecursionlimit(2000)

"""
GCD(assume a>=0, b>=0, a>=b )
"""
def gcd(a, b):
    if a < b:
        a, b = b, a
    if a == b:
        return a
    elif b == 0:
        return a
    else:
        return gcd(b, a % b)


"""
Extended Euclidean Algorithm (Iterative version) ( a >= b )

return (x, y, r) such that a * x + b * y = r = gcd(a, b)
loop invariant :
a * x_1 + b * y_1 = r_1
a * x_2 + b * y_2 = r_2

"""
def extended_euclid(a, b):

    if a == b:
        return 1, 0, a
    elif b == 0:
        return 1, 0, a
    else:
        x_1 = 1
        y_1 = 0
        r_1 = a

        x_2 = 0
        y_2 = 1
        r_2 = b

        while r_2 != 0:
            q = r_1 // r_2

            r_t = r_1 - q * r_2
            x_t = x_1 - q * x_2
            y_t = y_1 - q * y_2

            x_1, y_1, r_1 = x_2, y_2, r_2
            x_2, y_2, r_2 = x_t, y_t, r_t

        return x_1, y_1, r_1


"""
Multiplicative Inverse

x = a^-1 mod n
a * x mod n = 1

"""
def m_inv(a, n):
    x, y, r = extended_euclid(n, a % n)
    if r != 1:
        print("No multiplicative inverse")
        return
    else:
        return y % n

"""
miller-rabin prime test
Test if n is prime with error probability less than 2^n.
"""
Prime = 0
Composite = 1
def miller_rabin(n, s):
    if n == 2:
        return Prime
    elif n % 2 == 0:
        return Composite

    for _ in range(s):
        a = random.randint(1, n-1)
        if test(a, n) == True:
            return Composite

    return Prime

"""
subroutine for miller-rabin prime test
Perform the Fermat test and NSR (nontrivial square root) test.
"""
def test(a, n):
    bits = int_to_bin(n-1)
    k = len(bits) - 1
    t = 0

    while bits[k] == '0':
        t += 1
        k -= 1

    u = (n-1) >> t
    x = exp(a, u, n)
    for _ in range(t):
        _x = x
        x = (_x * _x) % n
        if x == 1 and _x != 1 and _x != n-1:
            return True

    if x != 1:
        return True
    else:
        return False

"""
int_to_bin
convert an integer to a binary representation
(the most significant bit becomes the 0-th bit)
"""
def int_to_bin(num):
    return list(bin(num))[2:]  # eliminate first two, ex) 0b00101001

"""
Modular exponentiation
returns a ^ b mod n
"""
def exp(a, b, n):
    c = 0
    f = 1
    bin_b = int_to_bin(b)
    k = len(bin_b)
    for i in range(k):   
        c = 2*c
        f = f*f % n
        if bin_b[i] == '1':
            c = c+1
            f = f*a % n
    return f

"""
RSA key pair generation
keylen: security parameter (desired number of bits in n)
    (keylen > 4)
"""
def keygen(keylen):
    bound = 1 << keylen//2   # upper bound for p and q.
    p = 2 * random.randint(bound//4, bound//2) - 1       # guarantee that p is odd.
    while miller_rabin(p, 50) == Composite:
        p = 2 * random.randint(bound//4, bound//2) - 1   # select new odd p.
    q = 2 * random.randint(bound//4, bound//2) - 1       # guarantee that q is odd.
    while miller_rabin(q, 50) == Composite:
        q = 2 * random.randint(bound//4, bound//2) - 1   # select new odd q.
    # Now p and q are odd primes.

    n = p * q
    phi_n = (p-1) * (q-1)  # euler totient function phi(n)

    # find e, satisfing gcd(phi(n), e) == 1, where 1 < e < phi(n)
    while gcd(phi_n, (e := random.randint(3, phi_n))) != 1:
        pass
    d = m_inv(e, phi_n)  # multiplicative inverse of Modular phi(n)

    return (e, d, n)

"""
RSA encryption
e, n: public key
M: plaintext < n
"""
def encrypt(M, e, n):
    return exp(M, e, n)

"""
RSA decryption
d, n: private key
C: ciphertext < n
"""
def decrypt(C, d, n):
    return exp(C, d, n)

"""
RSA test
"""
if __name__ == "__main__":
    e, d, n = keygen(512)
    print(e)
    M = 88
    C = encrypt(M, e, n)
    MM = decrypt(C, d, n)
    if M == MM:
        print("Example of RSA Algorithm works successfully")
        print("M={}, PU=({},{}), PR=({},{}), C={}, MM={}".format(M, e, n, d, n, C, MM))
    else:
        print("Example of RSA Algorithm works fail")
        print("M={}, PU=({},{}), PR=({},{}), C={}, MM={}".format(M, e, n, d, n, C, MM))