RSA 개념 정리 / e값이 65537인 이유

p = 충분히 큰 소수
q = 충분히 큰 소수
N = p * q
e = 65537

발견된 가장 큰 2의 소수이면서 phi랑 서로소이면서 페르마소수중에 가장 큰 소수

3가지의 조건을 성립하는 대중적인 공개키 

 

소인수 분해가 안될수록 RSA의 의미가 있으므로 쓰는걸로 추정.. 해외 사이트뒤져봐도 왜 저 조건을 성립하는 소수를 공개키의 일부로 주로 쓰게 되는지 모르겠다 

=>라고 작성했었는데 애초에 조건자체가 틀렸다 

 

페르마 소수라는것은 페르마가 소수를 구하는 법을 설명한것인데 

 [ Fn = 2²ⁿ + 1 ] 다음 공식을 가지는 수를 페르마 수 (Fermat number) 이라고 한다 

이를 통해 증명을 할 수 있다.

F0=3

F1=5

F2=17

F3=257

F4=65537

F5=4294967297=641x6700417 (즉 F5 는 소수가 아니다)

페르마는 F4보다 큰 어떤 수에 대해서도 소수라는 것을 증명하지 않았고,

F24 까지 수를 살펴본다면 많은 수가 합성수라는것이 알려졌다.

 

자 그럼 의문점이 생길건데 왜 RSA 비대칭키 암호문에 공개키를 가장큰 소수를 사용하는것일까? 

e값은 큰소수를 가지고 있어야 보안성이 높아지는데 65537은 작은 소인수를 가지지 않는 큰 소수이고 작은 소수 2와 3을 기반으로 하여 만들어진 소수 이기 때문에 e값을 65537로 설정하면 암호화 복호화 과정에서 빠른 계산을 제공하기 때문에 1과 자기 자신을 제외하고 다른수로는 나누어지지 않는 65537이 선택된 것이라고 한다

.

.

.

그렇게해서 
공개키 <e, N> 이 만들어진다 

phi = (p - 1) * (q - 1) (오일러의 피함수)

d = pow(e, -1, phi)

또는 d = inverse(e,phi) (개인키 구하기)
<d, N>(개인키)

pt = 암호화할 데이터 = 평문 (plaintext)
ct (ciphertext) = pow(pt, e, N)  (암호문) 공개키를 넣어 암호문을 만들고 

암호문이된 ct를 
pow(ct, d, N) (복호화) 암호문에 개인키를 넣어 복호화를 시킨다 

이런식으로 RSA 알고리즘이 동작한다.