[BerEditor] 큰수(Big Num) 계산기로 RSA 키쌍 및 암복호화 연산

[이 기능은 라이선스 버전 기능입니다]
라이선스가 필요한 분은 [프로그램 키 발급] 페이지에서 30일 라이선스 발급 가능합니다

RSA 기술에서 암호화 연산에는 아주 큰 숫자 연산 및 모듈라 연산이 주로 사용된다.
이 연산을 하기 위해서 BerEditor 메뉴에서 BN Calculator 를 이용하면 된다.

계산기에서 지원 하는 Base Group 에서 연산 방식은 3가지 이다.

- Number : 일반 정수 연산
- Modular : 모듈라를 이용한 연산
- GF2m : 갈루아 필드를 이용한 GF(2^m) 연산

이렇게 3가지 메뉴가 있다.
여기서 RSA 키상을 만드는것은 Number와 Modular 방식을 사용한다.
그리고 테스트로 사용하는 숫자 값은 헥사 표기이다.

계산기에서 입력값의 길이(오른쪽 읽기 표시)는 단순 문자의 개수이다.

보통 RSA 키 쌍은 두개의 큰 소수 P와 Q 를 만들고 이 값을 가지고 개인키와 공개키를 얻을 수 있다.
즉 큰 소수 P 와 Q를 노출은 곧 개인키를 노출되는 것으로 보면 되다.
그리고 공개로 PublicExponent 는 e = 010001 ( 10진수 65537) 을 사용한다.

여기 예제에서는 이해를 위해 짧은 키 길이 P와Q 256 비트를 사용한다.
즉 P와Q가 256 비트를 사용한다는 것은 P*Q 의 결과인 N이 512비트가 되어서 RSA 512 비트 키를 사용하는 것이다.

큰 소수 P와 Q 생성 및 공개키 구하기

• A : P 소수 생성 값
• B : Q 소수 생성 값
• A x B 버튼 : N값 구하기

그럼 N 값을 만들기 위해서는 P * Q 이므로 A * B 버튼을 눌러 주자
생성된 값

P (A 값) = D957E9E5E313B9E6EF0A112875037F227015BF81D235C61316E0F1CA10E5DFFD

Q (B 값) = C5C989AF683037D7D8D40BD1C47D2DAB5BFBF5B55CC5423E73804AC036C4B65B

N ( Result 값 ) = A7EBC1E984F70A21D8C3B8298D67B56CF10B796531FDBC8C096A0E97EFB33893FCF08CAFC79A3389B010F68447AC8A86D55BFB211FB5E28A90C827D64AA87CEF

여기서 계산된 ( e, N ) 값이 RSA 공개키 값이 된다.
만약 이미 만들어지 P와 Q값을 이용시는 A와 B영역에 복사해서 넣어 주어도 된다.

RSA 개인키를 구해 보자

개인키를 구하는 공식은 다음과 같다
$$ d ≡e^{-1} \, mod \, 𝜙(n) $$
먼저 개인키를 구하기 위해서 ϕ(n)=(p−1)×(q−1) 값을 구하자

참고로 실제 2048 Bits 이상의 개인키를 구하는 공식은 FIPS-186-4 에서는 아래 공식을 사용해야 한다.
$$  d ≡e^{-1} \, mod \, LCM(p-1, q-1) $$

LCM 구하기 참고

여기서는 예제로 위의 방식을 사용하였다.

• A 값에서 -1 버튼 을 누르면 (p-1) 계산
• B 값에서 -1 버튼 누른면 (q-1) 계산
• A x B 클릭 : ϕ(n) 값을 구하게 된다.

(P-1) = D957E9E5E313B9E6EF0A112875037F227015BF81D235C61316E0F1CA10E5DFFC

(Q-1) = C5C989AF683037D7D8D40BD1C47D2DAB5BFBF5B55CC5423E73804AC036C4B65A

ϕ(n) 결과값 = A7EBC1E984F70A21D8C3B8298D67B56CF10B796531FDBC8C096A0E97EFB338925DCF191A7C5641CAE832D98A0E2BDDB9094A45E9F0BADA390666EB4C02FDE698

개인키 d 값을 구하기

위 ϕ(n) 값을 M에 입력 그리고 A 에는 e값인 010001 입력후 A^-1 Mod M 버튼을 클릭 하면 개인키 d 값이 나온다.

E (A값) = 010001 ( 10진수 65537 )

ϕ(n) (M값) = A7EBC1E984F70A21D8C3B8298D67B56CF10B796531FDBC8C096A0E97EFB338925DCF191A7C5641CAE832D98A0E2BDDB9094A45E9F0BADA390666EB4C02FDE698

d (결과값) = 030E869C22A0809DB71D70F7C8AC2FA0490F0569B32C444764507AED871E83141F030B18F1547CA41DEFF707CD543D18063444EB8A474C7BA7432E5B56DE9A59

RSA 암호화

암호화 공식은 C = M^e mod N 이다.
RSA 암호화는 공개키 값만으로 만드는 값이다. 일반적으로 수신자의 공개키를 이용해 암호화 한다.
예제로 사용하는 메세지로 헥사 값 12345678 을 사용해서 암호화 해 보자

Message (A값) = 12345678  
e (B값) = 010001  
N 값 (M값) = A7EBC1E984F70A21D8C3B8298D67B56CF10B796531FDBC8C096A0E97EFB33893FCF08CAFC79A3389B010F68447AC8A86D55BFB211FB5E28A90C827D64AA87CEF

Cipher값 (Result값) = 50325882778093FD69C8A37D1B1FFCD8D60099D2DCEFBC3A6EADFF0EBD7B27320CAF505E81F8660C9534A49E2ECED3EC2EE928A7AC446FE5AA237CAEA0360F55 

RSA 복호화

복호화 공식은 M = C^d mod N 이다.
RSA 복호화는 개인키를 이용해 복호화 하게 된다.
그럼 암호문을 가지고 원문을 구해 보자.

Cipher (A값) =50325882778093FD69C8A37D1B1FFCD8D60099D2DCEFBC3A6EADFF0EBD7B27320CAF505E81F8660C9534A49E2ECED3EC2EE928A7AC446FE5AA237CAEA0360F55

d (B값) = 030E869C22A0809DB71D70F7C8AC2FA0490F0569B32C444764507AED871E83141F030B18F1547CA41DEFF707CD543D18063444EB8A474C7BA7432E5B56DE9A59

N ( M값) = A7EBC1E984F70A21D8C3B8298D67B56CF10B796531FDBC8C096A0E97EFB33893FCF08CAFC79A3389B010F68447AC8A86D55BFB211FB5E28A90C827D64AA87CEF

Plain (결과값) = 12345678

위 공식대로 값을 계산하게 되면 결과인 원문 12345678 을 구할 수 있다.

마무리

빅넘 연산기를 이용하여 간단히 RSA 키 쌍을 만들어 보았다.
이렇게 큰 소수 P 와 Q를 값을 알게 되면 개인키와 공개키를 구해지므로 p와 q값은 개인키와 같은 노출 되어서는 안되는 값이 된다.
여기서는 설명을 위해 512 비트의 짧은 길이를 사용 하였지만 실제에서는 2048 비트를 사용한다.
2048 비트로 테스트 할려면 위 설명에서 소수값 P와 Q생성 시 1024 비트를 선택 하여서 똑같이 하면된다.