분류 전체보기

[Dreamhack] bitcoin-master write-up

보호되어 있는 글입니다.

[Dreamhack][CTF Season 4] Proton Memo write-up

보호되어 있는 글입니다.

[Dreamhack] Robot Only - revenge write-up

보호되어 있는 글입니다.

[CryptoHack | DreamHack] Chinese Remainder Theorem (중국인의 나머지 정리)

크립토핵 설명보다 드림핵 설명이 이해하기 쉬웠다. 연습문제는 다음과 같다.x ≡ 2 mod 5 x ≡ 3 mod 11 x ≡ 5 mod 17 # Find the integer a such that x ≡ a mod 935 다음과 같이 풀 수 있다.from Crypto.Util.number import inverse p1 = 5 p2 = 11 p3 = 17 c1 = 2 c2 = 3 c3 = 5 m = p1*p2*p3 m1 = m // p1 m2 = m // p2 m3 = m // p3 n1 = inverse(m1, p1) n2 = inverse(m2, p2) n3 = inverse(m3, p3) x = pow(c1*m1*n1 + c2*m2*n2 + c3*m3*n3, 1, m) print(x) 또 다른 문제..

[CryptoHack] Modular Square Root (Tonelli-Shanks algorithm)

Legendre Symbol에서 우리는 숫자가 제곱근 모듈로 소수인지 여부를 확인하는 빠른 방법을 배웠다. 더 나아가서 이러한 근을 효율적으로 계산하는 알고리즘이 있다. 실제로 가장 좋은 것은 Tonelli-Shanks라고 불리며, 19세기에 이탈리아인에 의해 처음 기술되었고 1970년대에 Daniel Shanks에 의해 독립적으로 재발견되었다는 사실에서 이러한 이름을 얻었다. 2가 아닌 모든 소수는 p ≡ 1 mod 4 또는 p ≡ 3 mod 4 형식이다. p ≡ 3 mod 4의 경우 제곱근을 계산하기 위한 정말 간단한 공식은 페르마의 소정리에서 직접 도출할 수 있다. 여전히 p ≡ 1 mod 4 경우가 남아 있으므로 보다 일반적인 알고리즘이 필요하다. Tonelli-Shanks 알고리즘은 r^2 ≡ ..