곱셈 암호 이해하기!!

곱셈의 역원 (모듈러 역원)

 

일반적으로 곱셈의 역원이라 하면,

 

곱해서 1이 되는 수를 의미한다. 

 

따라서 a의 곱셈의 역원은 1/a 이라고 할 수 있다.

 

하지만, 여기서 우리가 구하는 역원은

 

나머지 연산의 곱셈의 역원, 즉 모듈러 역원이다. 

 

모듈러 역원은 a, b 두 수가 있을 때,

 

a의 n 배수를 b와 나누면 그 나머지가 1인 수를 말한다.

 

an  (mod b) ≡1

 

 

a와 b가 최대공약수가 1인 서로소라면 이는 모듈러 역원이라고 할 수 있다. 

 

 

곱셈 암호

 

이 모듈러 역원을 이용한 곱셈 암호가 있다.

 

곱셈 암호에서 암호화 키 a 가 있다면, 복호화 키는 a의 모듈러 역원이다. 

 

따라서 곱셈 암호로 암호화된 암호문과 암호화 키가 주어졌다면,

 

먼저 복호화 키를 구해주고 복호화해야한다.

 

 

식으로 이해를 해보자. 

 

 

C = 암호문 (Cypertext)
P = 평문,복호문 (Plaintext)
Kc =암호화키 
Kp =복호화키 (암호키의 역원)

 

이 식은 단순히, 암호문은 평문을 키로 암호화한 것이라는 뜻이다.

(평문 = 암호화되지 않은 문장)

 

이제 식을 평문에 대해 나타내보도록 하자.

 

우변에 p 만 남기고 나머지를 전부 좌변으로 옮겨주면 되는데, 

 

 

곱셈에서 항을 좌우로 이동시킬 때는 양변에 그 항의 역수를 곱해주는 것과 같다.

 

 

이걸 먼저 이해하면 좋을 것 같다.

 

우리는 흔히 6 = 2 * 3 에서 3을 좌변으로 옮기라고 하면

 

왼쪽 사진처럼 별 생각 없이 1/3을 곱한다.

 

하지만 사실 3이 시각적으로 넘어가는 게 아니라,

 

양 변에 3의 역수인 1/3이 각각 곱해지고

 

우변의 3과 1/3 은 곱하면 1이되어 사라지기 때문에 

 

6 * 1/3 = 2 의 꼴이 남는 것이다.  

 

 

 

따라서 위의 식에서도 Kc를 넘긴다고 생각하면 

 

헷갈리기 시작할테니, 양 변에 Kc의 모듈러 역원을 곱한다고 생각해야한다.

 

 

그럼 식은 이런 식으로 전개되고 더 깔끔하게 정리하면

 

 

이렇게 된다.

 

이 식을 그대로 읽으면, 

 

암호문에 복호키를 곱한 뒤 26에 대해 모듈러 연산을 거치면

 

평문을 얻어낼 수 있다는 뜻이된다.

 

(알파벳이 26개이기 때문에 mod 26을 하여 0~25, 총 26개 값 중 하나를 얻게 한다.)

 

 

 

곱셈 암호를 이용한 간단한 문제 풀이

 

 

아래 문제 풀이 과정을 보자.

 

암호문 JPEVAM 을 복호화 하여라 (암호화 키 : 7)

암호문은 C,  평문은 P, 암호화 키는 K0, 복호화 키는 K으로 표기

 

 

다음을 식으로 나타내면 C ≡ P * 7 (mod 26) 인데,

 

복호화를 해야하므로 

 

C * k  (mod 26)  ≡ P 이 식을 풀어주어야 한다. 

 

그러기 위해선 복호화 키 k 를 구해주어야 하고,

 

복호화 키는 gcd(7 , 26) = 1을 만족시키는 수와 같다.

 

유클리드 알고리즘을 진행해주면

https://studywithsheep.tistory.com/14

유클리드 호제법과 확장 유클리드 알고리즘

 

26 = 7*3 +5

7 = 5 *1 +2

5 = 2*2 +1

 

이를 대입이나 확장 유클리드 알고리즘으로 풀어주게 되면

 

26 * 3 + 7 * (-11) = 1 이므로

 

u = 3 v = -11 이 된다.

 

따라서 7의 복호화키는 -11이지만,

 

복호화키는 음수가 될 수 없기 때문에 

 

26과 더해주어야 한다. 

 

그렇게 되면 복호화 키는 15가 된다. 

 

 

이제 연산만 남았으니 이런 식으로 연산을 해주면 된다. 

 

알파벳은 a를 0으로 생각하고 하나씩 올라가면 된다. 

 

이런 식으로 다른 알파벳 p(15), e(4) , v(21), a(0), M(12)도 같은 방법으로 연산해주면

 

답은 Friday 라는 걸 알아낼 수 있다.