[[TableOfContents]] = OMS = * 김도엽 * Wiener's Attack의 구현(RSA) == 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의 곱셈 역원 * 는 공개키, 는 개인키 * 암복호화 과정 * c = m^e mod N * m' = c^d mod N * m = m' 하나, 증명은 생략 == Wiener's Attack이란? == * 개인키인 d가 충분히 작으면 사용할 수 있는 RSA 공격법 * 그 크기는 d < 1/3 * N^0.25 == 연분수 및 연분수 근사 == * Wiener's Attack은 연분수 근사를 이용한 공격 * 연분수 : 어떤 수를 자연수와 (분자가 1인 분수)의 합으로 나타내는 꼴이 반복되는 형태 * 연분수 근사 : 연분수로 표현된 수를 일정 항까지 근사에 사용함으로써 유의미한 근사값을 얻는 것 == 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 * 이 형태가 만들어지는데, 이 조건은 연분수 근사에서 충분히 근사가 가능한 조건 중 하나임 == 수행 과정 == * 우선 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를 알아냈음 == 코드 구현 == * [github | 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가 맞는지 확정지음 == 출처 == * [https://www.ams.org/journals/notices/199902/boneh.pdf?trk=199902boneh&cat=collection Twenty Years of Attakcs on the RSA Cryptosystem] * [https://en.wikipedia.org/wiki/Wiener%27s_attack Wiener's Attakc Wikipedia] = 엔젤스 캠프 = * 11월 11일 저녁 8시부터 12일 아침 8시까지 진행하는 자체 해커톤 * 오늘 20시까지 접수 받고 있음 = 스터디 = * [컴퓨터를구하자] : 시험 끝나고 1주 쉰 다음에 학교 기준 8, 9주차 한 번에 진행 = 프로젝트 = [ThisIsZeropage] : zp-portal 사이트를 만드는 프로젝트. 현재 엔캠 페이지 제작 완료