1.1. RSA에 대한 간단한 설명 ¶
- RSA는 공개키 암호 중 하나
- 수신자가 공개키와 개인키를 생성
- 그 중 공개키를 게시판 등을 통해 공개
- 송신자는 그 공개키로 평문을 암호화해서 전송
- 수신자는 암호문을 개인키로 복호화
- 전송 완료
- 수신자가 공개키와 개인키를 생성
- 키 생성 자세하게
- 512bits 두 소수 p, q를 생성
- N=p*q로 1024bits N을 계산
- phi(N)을 계산, 오일러 피 함수 성질을 이용해서 phi(N)=(p-1)(q-1)로 간단하게 계산 가능
- gcd(phi(N), e)=1을 만족하는 e 생성
- 보통 2^16+1인 65537을 사용(현재는 2^16-1인 65535를 사용한다고도 함)
- 보통 2^16+1인 65537을 사용(현재는 2^16-1인 65535를 사용한다고도 함)
- ed≡1(mod phi(N)) 인 d 생성
- d는 mod phi(N) 상에서 e의 곱셈 역원
- d는 mod phi(N) 상에서 e의 곱셈 역원
- <N, e>는 공개키, <N, d>는 개인키
- 512bits 두 소수 p, q를 생성
- 암복호화 과정
- c = m^e mod N
- m' = c^d mod N
- m = m' 하나, 증명은 생략
- c = m^e mod N
1.3. 연분수 및 연분수 근사 ¶
- Wiener's Attack은 연분수 근사를 이용한 공격
- 연분수 : 어떤 수를 자연수와 (분자가 1인 분수)의 합으로 나타내는 꼴이 반복되는 형태
- 연분수 근사 : 연분수로 표현된 수를 일정 항까지 근사에 사용함으로써 유의미한 근사값을 얻는 것
1.4. Wiener's Attack에서 어떻게 쓰이는가 ¶
- abs( e/phi(N) - k/d ) = 1/d*phi(N)
- 원래는 이 식이 성립함
- 하지만 공격자는 phi(N)을 모르고 N을 알고 있으므로 N을 통해서 근사를 진행하자는 아이디어
- 원래는 이 식이 성립함
- abs( e/N - k/d ) < 1/2*d^2
- 이 형태가 만들어지는데, 이 조건은 연분수 근사에서 충분히 근사가 가능한 조건 중 하나임
- 이 형태가 만들어지는데, 이 조건은 연분수 근사에서 충분히 근사가 가능한 조건 중 하나임
1.5. 수행 과정 ¶
- 우선 e/N을 연분수 형태로 변환
- a + 1/(b + 1/(c + 1/...)) 의 꼴로 연분수가 만들어 짐
- 이를 자연수만 가져와서 a, b, c, ... 리스트로 표현할 수 있음
- 이 리스트는 k/d의 후보들을 만드는데 참고해야 하는 리스트임
- a + 1/(b + 1/(c + 1/...)) 의 꼴로 연분수가 만들어 짐
- 앞에서 만든 연분수 리스트로 k/d가 될 수 있는 후보들을 만들어 줌
- 리스트의 앞에서부터 어디까지 가져와서 다시 분수 형태로 만드느냐가 중요함
- 예시를 들면 연분수가 1/(5+1/(29+1/(4+1/(1 + ... + 1/3)))) = 0, 5, 29, 4, 1, ..., 3의 리스트로 만들어 질 때, idx=1까지만 가져와서 1/5를 만들 수 있고, idx=2까지만 가져와서 29/146을 만들 수도 있음
- 특정 항까지 가져오고 그 뒤의 분수는 모조리 버려서 근사한다는 것
- (idx=0까지만 가져오면 k/d = 0인데, 이는 d의 정보를 가져올 수 없기 때문에 제외)
- 리스트의 앞에서부터 어디까지 가져와서 다시 분수 형태로 만드느냐가 중요함
- 여기서 나온 k와 d가 맞을 것이라고 생각하고 phi(N)을 계산
- phi(N) = (ed-1)/k
- 키 생성 과정에서 d를 구할 때 썼든 식을 변형하면 됨
- 키 생성 과정에서 d를 구할 때 썼든 식을 변형하면 됨
- phi(N)이 구해졌으므로, p와 q가 근인 이차 방정식을 짬
- x^2 - (N-phi(N)+1)x + N = 0
- 근과 계수의 관계에 의해서 이 식이 성립됨
- x^2 - (N-phi(N)+1)x + N = 0
- 근의 공식으로 p, q를 구했으므로, N과 맞는지 확인해서 맞으면 d를 알아냈음
1.6. 코드 구현 ¶
- https://github.com/Kredsya/wieners-attack
- 급하게 짜느라 여러 더러운 점이 있음 (수정 예정)
- 급하게 짜느라 여러 더러운 점이 있음 (수정 예정)
- t1, t2, ...로 시작해서 e, d = d, e로 끝나는 코드
- 확장 유클리드 호제법으로 d를 계산해주고 있는 코드며, 자세한 설명은 oms 하나 분량이라 생략
- e가 1/3 * N^0.25보다 작으므로 이 둘을 swap해 d를 작게 만들어줘서 취약점을 만들어줌
- 확장 유클리드 호제법으로 d를 계산해주고 있는 코드며, 자세한 설명은 oms 하나 분량이라 생략
- ingredient 리스트
- e/N을 연분수로 변환하여 리스트로 저장하는 변수
- k/d의 후보들을 만들 재료여서 ingredient라 이름 붙임
- e/N을 연분수로 변환하여 리스트로 저장하는 변수
- a, b = e, N 코드부터 ingredient = ingredient1: 코드까지
- 연분수를 만드는 과정, 이 과정은 유클리드 호제법과 유사함
- 그래서 a, b = (b, a%b)와 같은 코드가 있음
- 연분수를 만드는 과정, 이 과정은 유클리드 호제법과 유사함
- candidate = list()
- k/d 후보들을 이차원 리스트로 저장
- k/d 후보들을 이차원 리스트로 저장
- 다음 반복문에서 son, mom으로 분자, 분모를 표현
- candidate에 son, mom으로 append해서 분수를 표현
- candidate에 son, mom으로 append해서 분수를 표현
- lim_N을 계산해줘서 d의 근사 한계를 계산
- 마지막 반복문에서 predict k와 predict d를 candidate에서 받아서 검산
- 근의 공식으로 pred_p 와 pred_q를 계산하고 이것이 N이랑 동일한지 확인, 그래서 d가 맞는지 확정지음
- 근의 공식으로 pred_p 와 pred_q를 계산하고 이것이 N이랑 동일한지 확인, 그래서 d가 맞는지 확정지음
