[Cryptohack] General (Modular Arithmetic 1, 2, Modular Inverting)

Modular Arithmetic 1

문제 및 설명

몸을 숙이고 암호학자의 노트를 본다고 상상해 보세요. 다음과 같은 메모가 표시됩니다: 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 처음에는 그들이 미쳤다고 생각할지도 모릅니다. 아마도 이것이 오늘날 당신이 생각할 수 있는 많은 데이터 유출이 있는 이유일 것입니다. 하지만 이것은 모듈식 산술 모듈 12에 지나지 않습니다(비록 이상한 표기법이 있긴 하지만). 여러분은 그것을 모듈식 산술이라고 부르지 않았을 수도 있지만, 여러분은 시간을 알려주는 것을 배운 이후로 이런 종류의 계산을 해왔습니다. (이 방정식들을 다시 보고 시간을 더하는 것에 대해 생각해보세요.). 형식적으로 "시간 계산"은 합동성 이론에 의해 설명됩니다. 우리는 만약 a = b mod m이라면 두 정수가 합동 모듈이라고 말합니다. 이것을 말하는 또 다른 방법은, 우리가 정수 a를 m으로 나누면, 나머지는 b라는 것입니다. 이것은 m이 a를 나누면 (이것은 m | a로 쓸 수 있음) a ≡ 0 mod m이 된다는 것을 알려줍니다. 다음 정수를 계산합니다: 11 = x mod 6 8146798528947 =y mod 17 답은 두 수 중 더 작은 것 입니다.

풀이

print(min(11 % 6, 8146798528947 % 17))

답은 4이다.

 

Modular Arithmetic 2

문제 및 설명

우리는 최근 문제에서 교훈을 얻어 모듈러스 p를 선택했다고 상상할 것이고, p가 소수일 때 우리 자신을 제한할 것입니다. 정수 모듈 값 p는 Fp로 표시된 필드를 정의합니다. ✍계수가 소수가 아닌 경우 정수 모듈의 집합은 링을 정의합니다. 유한 필드 Fp는 정수 {0,1,...,p-1}의 집합이며, 덧셈과 곱셈 모두에서 집합의 모든 요소 a에 대해 a + b = 0 및 a * b = 1과 같은 역 요소 b가 있습니다. ✍덧셈과 곱셈의 확인 요소는 서로 다릅니다! 이는 연산자와 함께 작업할 때의 ID가 a + 0 = a 및 b * 1 = a와 같이 아무것도 하지 않아야 하기 때문입니다. p = 17을 선택한다고 가정해 보겠습니다. 3^17 mod 17을 계산합니다. 이제 5^17 mod 17에서도 동일하게 수행합니다. 7^16 mod 17에서 무엇을 얻을 것으로 예상합니까? 계산해 보세요. 이 흥미로운 사실은 페르마의 작은 정리로 알려져 있습니다. RSA 암호화를 검토할 때는 이 기능(및 일반화)이 필요합니다. 이제 소수 p = 65537을 구합니다. 273246787654^65536 mod 65537을 계산합니다. 계산기가 필요하시나요?

풀이

print((273246787654**65536) % 65537)

답은 1이다.

 

Modular Inverting

문제 및 설명

우리가 본 것처럼, 우리는 유한한 필드 Fp 내에서 요소를 더하고 곱하고, 항상 필드의 다른 요소를 얻을 수 있습니다. 필드의 모든 요소 g에 대해 g * d ≡ 1 mod p와 같은 고유 정수 d가 존재합니다. 이것은 g의 곱셈 역입니다. 예: 7 * 8 - 56 = 1  mod 11 그러면 역은 무엇입니까: 3 * d ≡ 1 mod 13? ✍우리가 방금 작업한 작은 정리를 생각해 보세요. 이것이 원소의 역을 찾는 데 어떻게 도움이 됩니까?

풀이

from Crypto.Util.number import inverse
print(inverse(3,13))

답은 9이다.

3* 9 = 1 mod 13이라고 생각 했을때

13*2+1이라고 생각하면 맞다.