문제 설명 애드리언은 symbol(아마 르장드르 기호)와 마이너스 기호를 통해 메시지를 암호화 하는 방법을 찾고 있어요. flag를 복구할 방법을 알고 있나요? 문제 풀이 문제는 그냥 이전 개념들을 사용해서 푸는 것으로 보인다. from random import randint a = 288260533169915 p = 1007621497415251 FLAG = b'crypto{????????????????????}' def encrypt_flag(flag): ciphertext = [] plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) for b in plaintext: e = randint(1, p) n = pow(a, e, p) if b == '1'..
개념 설명 중국인의 나머지 정리 (CRT) 중국인의 나머지 정리는 모듈리(mod p에서 p)가 서로소(coprime)일 경우 선형 합동 집합에 대한 특수한 해를 제공한다. 즉, 임의의 정수 집합 $a_i$와 pairwise(쌍) 서로소(paiwise coprime integers) $n_i$가 주어졌을 때 다음과 같은 선형 합동식이 성립한다. ! 참고로, "pairwise coprime integers"는 우리가 정수 집합 ${n_1, n_2, ..., n_i}$를 가지고 있을 때, 집합에서 선택된 모든 정수 쌍은: $\gcd(n_i, n_j) = 1$임을 의미한다. $ x \equiv a_1 \mod n_1$ $ x \equiv a_2 \mod n_2$ . . . $x \equiv a_n \mod n_..
개념 설명 모듈러 제곱근 르장드르 기호(Legendre Symbol)에서 우리는 숫자가 소수(prime) 모듈러의 제곱근인지를 결정할 수 있는 빠른 방법을 소개했다. 우리는 더 나아갈 수 있다: 그러한 제곱근을 효율적으로 계산하기 위한 알고리즘이 있다. Tonelli-Shanks라고 불리는 것이 있는데, 이것은 19세기에 이탈리아 인에ㅕ의해 처음 묘사되었고 1970년대에 Daniel Shanke에 의해 독립적으로 재발견 되었다는 사실에서 재미있는 이름을 얻었다. 2가 아닌 모든 소수는 모든 홀수가 다음과 같은 합동성을 띄기 때문에 $p \equiv 1 \mod 4$ 또는 $p \equiv 3 \mod 4$ 형식이다. 앞선 문제의 힌트처럼 $p \equiv 3 \mod 4$의 경우, 제곱근을 계산하기 위한..
개념 설명 르장드르 기호 2차 잉여에서 우리는 제곱근 정수 모듈러를 취하는 것이 무슨 의미인지 배웠다... 우리는 또한 제곱근을 가지는 것이 항상 가능한 것은 아니라는 것을 알았다. 이전의 경우 $p = 29$일때 간단한 루트 계산으로도? 충분히 빨랐지만 p가 커질수록 이 방법은 엄청나게 불합리해진다. 다행히도 르장드르 덕분에 정수가 한 번의 계산으로 2차 잉여인지 확인할 수 있는 방법이 있다. 다음에서 우리는 소수 p에 대한 모듈러 작업을 한다고 가정할 것이다. 르장드르 기호를 살펴보기 전에 2차 잉여의 흥미로운 성질을 보기 위해 잠시 돌아가보자. 이차 잉여 * 이차 잉여 = 이차 잉여 이차 잉여 * 이차 비잉여 = 이차 비잉여 이차 비잉여 * 이차 비잉여 = 이차 잉여 ! 이것을 쉽게 기억하는 방법은..
개념 설명 제곱 잉여 우리는 모듈러 연산에서 곱셈과 나눗셈에 대해서 살펴보았다. 그러나 제곱근 모듈러를 정수로 취하는 것은 뭘 의미할까? 해당 논의를 위해 모듈러 $p = 29$를 사용해보자. 우리는 정수 $a = 11$을 취하여 $a^2 = 5 \mod 29$ 임을 계산할 수 있다. $a = 11, a^2 = 5$로서 우리는 5의 제곱근이 11이라고 말한다.(?) 기분은 좋지만, 이제 18의 제곱근에 대해서 생각해보자. 위에서, 우리는 $a^2 = 18$인 정수 a를 찾을 필요가 있다는 것을 안다. 첫번째 아이디어는 $a=1$부터 시작하여 $a=p-1$까지 루프를 도는 것이다. 이 논의에서 p가 너무 크지 않으면 우리는 빨리 찾아낼 수 있을 것이다. 시도해보자. 이것을 코딩해보고 무엇을 찾는지 보자. ..
개념 설명 모듈러 연산 2 우리는 지난 문제로부터 모듈러 p를 고를 것입니다. 그리고 p가 소수일때의 경우로 제한합니다. 정수 모듈러 p는 체(field) $F_p$를 정의합니다. ! 만약 모듈러가 소수가 아니라면, 정수 모듈러 n 집합은 환(ring)을 형성합니다. 유한체 $F_p$는 정수 $\{0,1..., p-1\}$의 집합이며, 덧셈과 곱셈 모두에서 $a+b=0$, $a\times b = 1$과 같이 집합의 모든 원소 a에 대한 역원이 존재합니다. ! 덧셈과 곱셈의 항등원(identity element)는 서로 다릅니다! 항등원은 연산자와 함께 동작할 때 아무것도 수행하지 않아야 합니다. : $a+0 = a$ : $a \times 1 = a$ $p = 17$을 선택한다고 가정합시다. $3^{17}..
개념 설명 모듈러 연산 당신이 몸을 숙이고 암호학자의 노트를 본다고 상상해보라. 여백에 다음과 같은 참고 사항이 표기되어 있는 게 보인다. 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 처음엔 그들이 미쳤다고 생각할지도 모른다. 이것이 오늘날 많은 데이터유출의 이유라고 생각될 수도 있겠지만, 이것은 모듈러 12에 대한 모듈러 연산에 지나지 않는다. (비록 다소 엉성한 표기법일지라도 말이다.) 당신은 모듈러 연산을 사용해본 적이 없다고 할 수도 있겠지만, 당신은 시간을 말하는 법을 배운 이후로 이런 종류의 계산을 해오고 있다. (위 식을 다시 보고 시간을 더하는 것에 대해 생각해보라.) 형식적으로 "시간 계산"은 합동식 이론에 의해 설명된다. 우리는 두 정수가 $a \equiv b \bmod m$..
https://thfist-1071.tistory.com/entry/C-%EC%96%B8%EC%96%B4-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%A6%9D%EB%AA%85-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A1%9C-%EA%B5%AC [C 언어] 유클리드 호제법 증명과 재귀함수 구현 유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요. 유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다. 여담으로 최소공배수는 (두 수의 곱/gcd) thfist-1071.tistory.com 알고리즘, 자료구조 카테고리에 포함되어 ..
