background

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

[CryptoHack] Modular Arithmetic 2

정수 모듈로 p는 Fp로 표시된 필드를 정의한다. 소수가 아닌 경우 정수 모듈로 n 집합은 링을 정의한다. (순환한다는 의미인 듯) 유한 필드 Fp는 정수 {0,1,...,p-1}의 집합이고, 덧셈과 곱셈 모두 집합의 모든 요소 a에 대해 역 요소 b가 있다. a + b = 0 a * b = 1 덧셈과 곱셈의 항등 요소가 다르다는 점에 유의해야 한다고 한다. 이는 연산자로 작동할 때 항등식이 아무 작업도 수행하지 않아야 하기 때문이라고 한다. (항등식을 만족해야 한다는 의미인 듯) a + 0 = a a * 1 = a 연습문제는 다음과 같다. p가 17일 경우 다음을 계산해보라고 한다. 3^17 mod 17 5^17 mod 17 7^16 mod 17 해당 내용은 페르마의 소정리로 알려져 있다고 한다. 위키..

[CryptoHack] Modular Arithmetic 1

다음과 같은 식이 있다. 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 이 연산은 모두 모듈러12 연산으로도 설명할 수 있다고 한다. 위키의 모듈러 연산에 대한 정의는 다음과 같다. 컴퓨팅에서 모듈로 연산은 한 숫자를 다른 숫자로 나눈 후 나눗셈의 나머지 또는 부호 있는 나머지를 반환합니다. 두 개의 양수 a와 n이 주어지면 모듈로 n은 a를 n으로 나눈 유클리드 나눗셈의 나머지입니다. 여기서 a는 피제수이고 n은 약수입니다 다음은 칸 아카데미에서 설명하는 내용인데 모듈러12 연산에 대해 설명하고 있다. a ≡ b mod m이면 두 정수가 modulo m과 합동이라고 말한다. 이것을 다르게 표현하면 "정수 a를 m으로 나눌 때 나머지가 b이다." 로 표현할 수 있다. 이것은 a가 m으로 나누어 ..

[CryptoHack] Extended GCD

양의 정수 a와 b가 있을 때, 확장된 유클리드 알고리즘은 다음과 같은 정수 u,v를 찾는 효율적인 방법이다. a * u + b * v = gcd(a,b) 나중에 RSA를 해독하는 방법을 배울 때 공개 지수의 모듈러 역수를 계산하기 위해 이 알고리즘이 필요하다고 한다. 확장된 유클리드 알고리즘에 대한 자세한 내용은 아래 페이지를 확인하라고 한다. https://web.archive.org/web/20230511143526/http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html Extended Euclidean Algorithm Formed in 2009, the Archive Team (not to be confused with the ar..