background/crypto

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

[CryptoHack] Greatest Common Divisor (GCD)

최대 공약수(GCD)는 두 양의 정수(a,b)를 나누는 가장 큰 수이다. a = 12, b = 8인 경우 a의 약수: {1,2,3,4,6,12}와 b의 약수: {1,2,4,8}을 계산할 수 있다. 이 둘을 비교하면 gcd(a,b) = 4임을 알 수 있다. a = 11, b = 17의 경우를 보면, a와 b는 모두 소수이다. 소수는 자신과 1만 약수로 가지므로 gcd(a,b) = 1이다. 임의의 두 정수 a,b에 대해 gcd(a,b) = 1이면 a와 b는 서로소 정수라고 말한다. a와 b가 소수이면 서로소(coprime)이다. a가 소수이고 b a인 경우는 b가 a의 배수일 때 a를 공약수로 가지므로 서로소가 아니게 될 것이다) 두 정수의 GCD를 계산하는 많은 ..