Contents
1
.
OMS
1.1
.
RSA에 대한 간단한 설명
1.2
.
Wiener's Attack이란?
1.3
.
연분수 및 연분수 근사
1.4
.
Wiener's Attack에서 어떻게 쓰이는가
1.5
.
수행 과정
1.6
.
코드 구현
1.7
.
출처
2
.
엔젤스 캠프
3
.
스터디
4
.
프로젝트
1
.
OMS
¶
김도엽
Wiener's Attack의 구현(RSA)
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를 사용한다고도 함)
ed≡1(mod phi(N)) 인 d 생성
d는 mod phi(N) 상에서 e의 곱셈 역원
<N, e>는 공개키, <N, d>는 개인키
암복호화 과정
c = m^e mod N
m' = c^d mod N
m = m' 하나, 증명은 생략
1.2
.
Wiener's Attack이란?
¶
개인키인 d가 충분히 작으면 사용할 수 있는 RSA 공격법
그 크기는 d < 1/3 * N^0.25
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의 후보들을 만드는데 참고해야 하는 리스트임
앞에서 만든 연분수 리스트로 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를 구할 때 썼든 식을 변형하면 됨
phi(N)이 구해졌으므로, p와 q가 근인 이차 방정식을 짬
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를 작게 만들어줘서 취약점을 만들어줌
ingredient 리스트
e/N을 연분수로 변환하여 리스트로 저장하는 변수
k/d의 후보들을 만들 재료여서 ingredient라 이름 붙임
a, b = e, N 코드부터 ingredient = ingredient
1:
코드까지
연분수를 만드는 과정, 이 과정은 유클리드 호제법과 유사함
그래서 a, b = (b, a%b)와 같은 코드가 있음
candidate = list()
k/d 후보들을 이차원 리스트로 저장
다음 반복문에서 son, mom으로 분자, 분모를 표현
candidate에
son, mom
으로 append해서 분수를 표현
lim_N을 계산해줘서 d의 근사 한계를 계산
마지막 반복문에서 predict k와 predict d를 candidate에서 받아서 검산
근의 공식으로 pred_p 와 pred_q를 계산하고 이것이 N이랑 동일한지 확인, 그래서 d가 맞는지 확정지음
1.7
.
출처
¶
Twenty Years of Attakcs on the RSA Cryptosystem
(https://www.ams.org/journals/notices/199902/boneh.pdf?trk=199902boneh&cat=collection)
Wiener's Attakc Wikipedia
(https://en.wikipedia.org/wiki/Wiener%27s_attack)
2
.
엔젤스 캠프
¶
11월 11일 저녁 8시부터 12일 아침 8시까지 진행하는 자체 해커톤
오늘 20시까지 접수 받고 있음
3
.
스터디
¶
컴퓨터를구하자
: 시험 끝나고 1주 쉰 다음에 학교 기준 8, 9주차 한 번에 진행
4
.
프로젝트
¶
ThisIsZeropage
: zp-portal 사이트를 만드는 프로젝트. 현재 엔캠 페이지 제작 완료
Retrieved from http://wiki.zeropage.org/wiki.php/정모/2022.11.09
last modified 2022-11-16 03:40:44