GCD , modular inverse , affine cipher , vigenere cipher

modular arithmetic ( clock arithmetic)

연산 기호는 mod로 나타내며 파이썬에서는 %를 사용한다. 이는 두 수의 greatest common divisor(GCD,최대공약수)를 구하는데 사용한다.

---

greatest common divisor를 찾기 위한 factor찾기

24의 factors는 1,24 , 2,12 , 3,8 , 4,6이다. 항상 1과 자기 자신은 가진다.
비슷하게 30은 1,30 , 2,15 , 3,10 , 5,6이 존재하며, 이들의 최대공약수는 6이다.

---

euclid's algorithm

GCD를 구하는 방법. 만약 양의 정수 a,b(a>b)존재시...
a = bq + r ( 0 <= r < b )이면, a,b의 최대공약수는 b,r의 최대 공약수와 같다. r=0이면 a,b의 GCD는 b이다.
즉, gcd(a,b) = gcd(b,r)

---

 

증명 gcd(a,b) = G

let, 두 정수 A,b의 최대 공약수를 G라고 하자.
G는 공약수이니 두 서로소 a,b에 대해 다음식이 성립

1. A = aG , B = bG

 

let, A를 B로 나눈 나머지를 r, 몫을 q라고 하면 다음식이 성립

1. A = qB + r ( 단, 0 <= r < |B| )

 

그리고 위의 2개의 식을 이용하면 다음이 성립

1. aG = qbG + r
2. r = aG - qbG = G(a - qb)

---

def gcd(a , b):
    if a>b:
        tmp=a
        a=b
        b=tmp
    while a!=0:
        a,b = b%a , a
    return b
print(gcd(24,32)) # 8출력
print(gcd(32,24)) # 8출력

---

---

multiplicative cipher

카이사르 암호와 비슷하지만, 카이사르 암호는 key에 의해 addition을 했다면 이는 multiplication을 한다.
곱하다보면 카이사르처럼 범위를 넘어가는 wraparound issue가 존재하지만, 이때 mod를 사용한다.
multiplicative cipher는 나중에 mod시에 소수로 인해서 66개의 문자에 대해서 20개의 키밖에 사용할 수 없다.
복호는 key값을 다시 나누는 과정을 거친다.( key의 역원을 곱함 )

• encrypt: cipher_char = ( plain_char * key_value ) mod 26
• decrypt: plain_char = (cipher_char * key_value^-1 ) mod 26

 

---

modular inverse

• (a*a^-1) = 1 (mod n). 여기서 n은 symbol_set size이며 a는 해당 글자의 idx이다.
• (a * i ) % m == 1 이라고 생각하면 됨. i가 a^-1이며 m이 n이다.
  • 시저 암호(Caesar Cipher) : C = (P + K) mod symbol_set_size
  • 곱셈 암호(Multiplication Cipher) : C = (P * K) mod symbol_set_size
  • 아핀 암호(Affine Cipher) : C = (P * K1 + K2) mod symbol_set_size

def find_modular_inverse( a , symbol_set_size): # a는 모듈러 역원을 찾을 숫자, 
    if gcd( a , symbol_set_size)!=1:
        print("a와 symbol_set_size는 서로소여야함.")
    # extended euclid's algorithm을 이용해서 모듈러 역원을 찾음.
    u1 , u2 , u3 = 1 , 0 , a # u1,u2는 첫번째 숫자의 계수, u3는 첫번째 숫자
    v1 , v2 , v3 = 0 , 1 , symbol_set_size # v1,v2는 두번째 숫자의 계수, v3는 두번째 숫자
    # v3가 0이 될때까지...
    while v3 != 0:
        q = u3 // v3 #  몫을 구함
        # 위에 표를 보면 더 이해 쉬움
        v1 , v2 , v3 , u1 , u2 , u3 = ( u1 - q *v1 ) , ( u2 - q * v2 ) , ( u3 - q * v3 ) , v1 , v2 ,v3
    return u1 % symbol_set_size

---

affine cipher

아핀 암호(Affine Cipher) : C = (P * K1 + K2) mod symbol_set_size
단, k1과 symbolSetSize는 서로소 관계 multiplicative cipher와 caesar cipher를 조합한것이다.
복호화를 위해서는 modular inverse가 필요하다.

• key A와 key B를 입력 받는다.
• encrypt : plain_text -> multiple key A -> add key B -> mod by symbol_set size -> cipher_text
• decrypt : cipher_text -> sub key B -> multiple by mod inverse of key A -> mode by symbol_set size -> plain_text
  • 1 isn’t the modular inverse of 5 mod 7, (5 * 1) % 7 = 5.
  • 2 isn’t the modular inverse of 5 mod 7, (5 * 2) % 7 = 3.
  • 3 is the modular inverse of 5 mod 7, (5 * 3) % 7 = 1. .

---

 

polyalphabetic cipher 다중 치환 암호

위에까지 나온 치환 암호는 단일 문자 치환( monoalpabetic substitution)이였다.
이것들은 단어의 출연 빈도수를 이용해서 평문을 유추하는 것이 가능.
이를 좀 더 보완하기 위해 다중 치환 암호가 나옴.
이 방법은 plain text의 문자의 빈도와 cipher text에서 사용되는 문자의 빈도를 다르게 하는 방법

 

---

 

vigenere cipher 비제네르 암호

16세기에 만들어진 다중 치환 암호
단일 치환의 암호를 보안하기 위해 만들어짐
만약 키가 ABCD이면 plain text에 순서대로 1,2,3,4더하고 다시 1,2,3,4더하는 방식으로 사이클이 돌아감

def generate_key( text , key ):
    key = list(key) # 우선 키를 리스트로 만들어줌
    if len(text) == len(key):
        return key
    else:
        for i in range( len(text) - len(key) ):
            key.append( key[ i%len(key) ] )
    return "".join(key)

def vigenere_encrypt( plain_text , keyword ):
    key = generate_key( plain_text , keyword )
    cipher_text = []

    for i in range( len(plain_text) ):
        x = ( ord( plain_text[i] ) + ord(key[i]) ) %128
        #x += ord('A')
        cipher_text.append(chr(x))
    return "".join(cipher_text)

def vigenere_decrypt( cipher_text , keyword ):
    key = generate_key( cipher_text , keyword)
    plain_text = []
    for i in range(len(cipher_text)):
        x = (ord(cipher_text[i]) - ord(key[i]) + 128 ) %128
      #  x += ord('A')
        plain_text.append(chr(x))
    return "".join(plain_text)

plain_text = "THISisTESTtext"
keyword = "JUPYTER"

encrypted_text = vigenere_encrypt( plain_text , keyword)
print(f"encrypted text is {encrypted_text}")
decrypted_text = vigenere_decrypt(encrypted_text , keyword)
print(f"decrypted text is {decrypted_text}")