현재 암호키의 안전한 분배 및 관리문제를 해결하기 위해 널리 이용되고 있는 RSA암호법은 1978년에 세 사람(Rivest, Shamir, Adleman)에 의해 발명된 것으로, 아주 큰 자리(140자리 이상)의 자리수가 비슷하지만 두 수의 차가 큰 서로 다른 두 소수 p, q (n=pq)를 이용한 암호 방법이다. 사용자는 mod Φ(n) =(p-1)(q-1) 에 관해 서로소인 e 를 개인 공개키로 선택하고 e와 n을 공개한다. 사용자가 p, q를 알고 있다면, 정수론의 약간의 지식(유클리트 알고리즘)을 이용하여 e*d ≡1 (mod (p-1)(q-1)) 인 정수d를 개인 비밀키로 택할 수 있고, 이들을 이용하여 암호화와 복호화를 하는 방법이다.
암호화방법은 문자를 숫자로 바꿔 이어 놓고 나서, 적당한 숫자블럭으로 나누어서 각 블럭을 mod n에 관해 공개키e로 거듭제곱하여 누구나 암호화한다. 복호화는 개인만이 아는 비밀키d를 사용하여 mod n에 관해 거듭제곱하면 원래의 숫자가 나오는 방법이다. 이처럼 간단하게 암호화와 복호화가 되는 것이 왜 암호를 깨기가 지극히 어려울까? 이는 p, q 와 d 중 하나만 알면 간단히 암호가 깨지는데, n과 공개키 e는 알려져 있으므로, d를 구하기 위해서는 (p-1)(q-1)을 알아야 하고, p와 q를 알기 위해서는 n을 인수분해해야 한다. 즉 n을 인수분해하면 모두를 알 수 있는데, 만약 n이 200자리가 넘으면 아주 좋은 수퍼컴퓨터로 계산하여도 1 만년 이상이 걸린다. 이것 때문에 RSA암호법이 실용화될 수 있다.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021
컴퓨터 자판의 아스키코드는 다음과 같다. 단, space=32
[자료1]
-1회용 암호의 그 자료와 동일함
[/자료1]
1 . 평문(영어 문장)과 숫자를 아래 5군데(1번~5번)
I'm Negi
2 . 991 소수p
3. 919 소수q
4. 881 φ(pq)와 서로소인 수
5. 5 나눌 block의 자리수
(주의: 자리수는 pq의 자리수보다 작은 수여야 함. 왜?, (예) pq=100 이면 크기는 2이하를 선택)
pq = 910729 (공개키), e = 881 (공개키)
φ(pq) = 908820 =(p-1)(q-1), d = (비밀키: 46421
e의 역원(mod φ(pq)))
♤서로소판정: (φ(pq),e) = 1 이므로
φ(pq)와 e는 서로소 입니다. [서로수가 안될경우 안됩니다.]
평문을 숫자(위의 아스키코드에서 32를 뺀 00-94에 해당하는 숫자:
space키와 자판문자)로 바꾼 것.
41 07 77 00 46 69 71 73
숫자평문을 블럭의 자리수만큼씩 나눈것.
마지막 자리수가 맞지 않으면 0(space key에 해당)으로 채움:
41077 70046 69717 30000
위의 각 block를 (block)^(공개키 e) (mod 공개키 pq)로 계산한
숫자암호문
857903 553059 197771 789540
1. 숫자암호문을 복사하여 입력하고 나머지(2번~5번)를 입력하세요:
857903 553059 197771 789540
2. 991 왼쪽의 소수p
3. 919왼쪽의 소수q
4. 46421처음 상태로 가기 버튼 아래의 비밀키 d
5. 5왼쪽의 나눌 block의 자리수
pq = 910729 (공개키), d =46421 (비밀키)
φ(pq) = 908820 =(p-1)(q-1), e = 881 (공개키)
♤서로소판정: (φ(pq),e) = 1 이므로
φ(pq)와 e는 서로소 입니다.
숫자암호문의 각 block를
(block)^(비밀키 d) (mod 공개키 pq)로 계산한 숫자복호문
41077 70046 69717 30000
위 숫자복호문을 2자리씩 분리하여 아스키코드 숫자로 바꿀 준비
41 07 77 00 46 69 71 73 00 00
위 숫자에 32를 더하여 아스키코드문자로 변환한
복호문
I'm Negi
암호화방법은 문자를 숫자로 바꿔 이어 놓고 나서, 적당한 숫자블럭으로 나누어서 각 블럭을 mod n에 관해 공개키e로 거듭제곱하여 누구나 암호화한다. 복호화는 개인만이 아는 비밀키d를 사용하여 mod n에 관해 거듭제곱하면 원래의 숫자가 나오는 방법이다. 이처럼 간단하게 암호화와 복호화가 되는 것이 왜 암호를 깨기가 지극히 어려울까? 이는 p, q 와 d 중 하나만 알면 간단히 암호가 깨지는데, n과 공개키 e는 알려져 있으므로, d를 구하기 위해서는 (p-1)(q-1)을 알아야 하고, p와 q를 알기 위해서는 n을 인수분해해야 한다. 즉 n을 인수분해하면 모두를 알 수 있는데, 만약 n이 200자리가 넘으면 아주 좋은 수퍼컴퓨터로 계산하여도 1 만년 이상이 걸린다. 이것 때문에 RSA암호법이 실용화될 수 있다.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021
컴퓨터 자판의 아스키코드는 다음과 같다. 단, space=32
[자료1]
-1회용 암호의 그 자료와 동일함
[/자료1]
1 . 평문(영어 문장)과 숫자를 아래 5군데(1번~5번)
I'm Negi
2 . 991 소수p
3. 919 소수q
4. 881 φ(pq)와 서로소인 수
5. 5 나눌 block의 자리수
(주의: 자리수는 pq의 자리수보다 작은 수여야 함. 왜?, (예) pq=100 이면 크기는 2이하를 선택)
pq = 910729 (공개키), e = 881 (공개키)
φ(pq) = 908820 =(p-1)(q-1), d = (비밀키: 46421
e의 역원(mod φ(pq)))
♤서로소판정: (φ(pq),e) = 1 이므로
φ(pq)와 e는 서로소 입니다. [서로수가 안될경우 안됩니다.]
평문을 숫자(위의 아스키코드에서 32를 뺀 00-94에 해당하는 숫자:
space키와 자판문자)로 바꾼 것.
41 07 77 00 46 69 71 73
숫자평문을 블럭의 자리수만큼씩 나눈것.
마지막 자리수가 맞지 않으면 0(space key에 해당)으로 채움:
41077 70046 69717 30000
위의 각 block를 (block)^(공개키 e) (mod 공개키 pq)로 계산한
숫자암호문
857903 553059 197771 789540
1. 숫자암호문을 복사하여 입력하고 나머지(2번~5번)를 입력하세요:
857903 553059 197771 789540
2. 991 왼쪽의 소수p
3. 919왼쪽의 소수q
4. 46421처음 상태로 가기 버튼 아래의 비밀키 d
5. 5왼쪽의 나눌 block의 자리수
pq = 910729 (공개키), d =46421 (비밀키)
φ(pq) = 908820 =(p-1)(q-1), e = 881 (공개키)
♤서로소판정: (φ(pq),e) = 1 이므로
φ(pq)와 e는 서로소 입니다.
숫자암호문의 각 block를
(block)^(비밀키 d) (mod 공개키 pq)로 계산한 숫자복호문
41077 70046 69717 30000
위 숫자복호문을 2자리씩 분리하여 아스키코드 숫자로 바꿀 준비
41 07 77 00 46 69 71 73 00 00
위 숫자에 32를 더하여 아스키코드문자로 변환한
복호문
I'm Negi
llllllllllll 1Gbps Line