background/crypto

[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 ≡ ..

[CryptoHack] Legendre Symbol (르장드르 기호)

이전 강의(Quadratic Residues, 제곱 잉여)에서는 모듈로 체계에서 이차 잉여가 존재하지만 모든 수가 그렇진 않다는 것을 배웠다. 이번 강의에서는 Legendre Symbol(르장드르 기호)에 대해 설명한다. 르장드르 기호는 어떤 수가 제곱 잉여인지 여부를 판단할 때 사용한다. 위키의 설명은 다음과 같다. 또 다음과 같은 식도 성립한다고 한다. 제곱 잉여(1) * 제곱 잉여(1) = 제곱 잉여(1) 제곱 잉여(1) * 제곱 비잉여(-1) = 제곱 비잉여(-1) 제곱 비잉여(-1) * 제곱 비잉여(-1) = 제곱 잉여(1) 크립토핵에선 르장드르 기호를 다음과 같이 정리해준다. [정의] (a / p) = 1 (모듈러 p에서 a가 제곱 잉여이고, a ≢ 0 mod p) (a / p) = -1 (모..

[CryptoHack] Quadratic Residues (제곱 잉여)

Quadratic Residues는 제곱 잉여 또는 이차 잉여 라고 부른다. 위키에서 다음과 같이 설명한다. 크립토핵에선 모듈로 p = 29를 예시로 든다. 정수 a = 11을 취하고 a^2 = 5 mod 29를 계산해보자. a % p = 11, a^2 % p = 5이므로 5의 제곱근은 11이다. 이번엔 18의 제곱근을 구해보자. 제곱근을 찾기 위해 a^2 = 18 mod 29를 만족하는 수 a를 찾아야 한다. 하지만 0 ~ 28까지의 수 중에서 만족하는 수가 없다. 이렇게 식 a^2 = x mod p 를 만족하는 a가 존재할 때 정수 x는 a에 대한 제곱 잉여라고 할 수 있다. 위키에서 이러한 제곱 잉여는 홀수인 소수 p에 대하여 (p-1)/2 개가 존재한다고 한다. 연습 문제는 다음과 같다. # 아래..

[CryptoHack] Modular Inverting (모듈로 역수)

유한한 필드 Fp 내에서 우리는 요소를 더하고, 곱하고, 항상 필드의 다른 요소를 얻을 수 있다. 필드의 모든 요소 g에 대해 g * d ≡ 1 mod p인 고유한 정수 d가 존재한다. 이것은 g의 곱셈의 역수이다. (d = 1/g) 모듈로 역수의 예시는 다음과 같다. 7 * 8 = 56 ≡ 1 mod 11 연습 문제는 다음과 같다. 3 * d ≡ 1 mod 13 mod 13 에서 3*d = 1을 만족하는 수(모듈로 역수)를 찾으면 된다. 이는 3*d % 13 = 1을 만족함을 의미한다. 계산해보면 d는 9이다. 파이썬의 inverse 함수로도 구할 수 있다. from Crypto.Util.number import inverse print(inverse(3,13)) 레퍼런스 https://cryptoha..