![[프로그래밍] 암호화 프로그램-1](http://images.happyhaksul.com/thumb/481/480824-0001.gif)
![[프로그래밍] 암호화 프로그램-2](http://images.happyhaksul.com/thumb/481/480824-0002.gif)
![[프로그래밍] 암호화 프로그램-3](http://images.happyhaksul.com/thumb/481/480824-0003.gif)
![[프로그래밍] 암호화 프로그램-4](http://images.happyhaksul.com/thumb/481/480824-0004.gif)
![[프로그래밍] 암호화 프로그램-5](http://images.happyhaksul.com/thumb/481/480824-0005.gif)
![[프로그래밍] 암호화 프로그램-6](http://images.happyhaksul.com/thumb/481/480824-0006.gif)
![[프로그래밍] 암호화 프로그램-7](http://images.happyhaksul.com/thumb/481/480824-0007.gif)
분야
hwp● Presented problems
● 문제에 대한 접근
● 암호화 & 암호 해독 프로그램
● 주어진 방법의 문제점
Part 2. 향상된 암호화 프로그램
● 향상된 암호해석 기법
● 모듈함수 기법& 유클리드 호제법
● 손으로 풀어보기
● 대략적인 알고리즘 & 순서도
● 스크립트 파일 & 보조 설명
● 고찰
모듈함수를 통해서 암호화 시킨 문서를 해독하는 과정으로서, 위에서 기술하였던 예문을 이어서 설명해 보겠다.
97*17+23≡P(mod128)을 변형시켜서 97*17≡P-23(mod128)으로 나타낸다. 여기서 중요한 점은 모듈함수 수식구문에서 덧셈이나 뺄셈은 결과 값에 영향을 미치지 않기 때문에 더해주었던 것을 그대로 역으로 빼주는 것이다. 이어서 위의 식을 97*17*≡(P-23)*(mod128)로 나타낼 수 있다. 여기서 은 mod128에 대한 17의 역원을 나타낸다. 따라서 97≡(P-23)*(mod128)로 정리 할 수가 있다. 결론적으로 복호화는 다음과 같이 나타낼 수 있다. (P-23)*=O (mod128) [O:원문, Original]
-모듈함수의 역원 구하기
모듈함수의 역원을 구하기 위해서 유클리드 호제법을 이용한다. 위의 예문에서 의 값을 구하기로 해본다.
① 먼저 128과 17의 gcd(128,17)을 유클리드 호제법으로 구한다.
128=17*7+9 gcd(128,17)
17=9*1+8 gcd(9,8)
9=8*1+1 gcd(8,1) -----Equation2
8=1*8+0
2. Equation2의 한항에 1만 남기고 다 이항한 후, 유클리드 호제법을 역으로 시행한다.
1=8*(-1)+9
=(17-9*1)*(-1)+9=9*(-2)+17*(-1)
=(128-17*7)*(-2)+17*(-1)=17*(-15)+128*(-2)
즉, 17*(-15)+128*(-2)=17*(-15)=1 (mod128)
17*X=1 (mod128)
17*=1 (mod128)
따라서 mod128에 대한 17의 역원 =-15이다.
양수로 나타내기 때문에 -15=113(mod128), 즉 =113(mod128)임을 알 수 있다.
※유클리드의 호제법
- 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면,
