문제 AES는 모든 좋은 블록 암호와 같이 “키가 있는 순열”을 수행합니다. 이것은 모든 가능한 입력 블록을 고유한 출력 블록으로 매핑하며, 키가 어떤 순열을 수행할지 결정합니다. “블록”이라는 용어는 그저 일정 수의 비트 또는 바이트를 가리키며, 이는 어떤 종류의 데이터든 나타낼 수 있습니다. AES는 블록을 처리하고 다른 블록을 출력합니다...

문제 소수 p,q를 얻기 위해 다음 방정식을 재배열하세요. $N = p * q$ $c1 = (2p + 3q)^{e1}\,mod\,N$ $c2 = (5p + 7*q)^{e2}\,mod\,N$ 풀이 이번 문제는 제공되는 $N, e1, e2, c1, c2$ 값을 가지고 $p, q$ 값을 구하는 문제입니다. 문제를 풀기위해 아래 개념을 알아...

문제 중국인의 나머지 정리는 모듈러가 서로 소인 일련의 선형 합동에서 고유한 해를 제공합니다. 즉, 일련의 임의의 정수 $a_i$와 서로소인 $n_i$가 주어진다고 할 때, 다음의 선형 합동이 유지되는 경우: 참고로 “서로소인 정수 쌍”이라는 말은 ${n_1, n_2, …, n_i}$의 정수 집합이 주어졌을 때, 집합에서 선택한 모든 정수 ...

문제 르장드르 기호에서는 소수에 대한 모듈러 제곱근이 있는지를 판단하는 빠른 방법을 소개했습니다. 더 나아가서, 이러한 제곱근을 효율적으로 계산하는 알고리즘도 있습니다. 실제로 가장 효율적인 알고리즘은 19세기에 이탈리아인에 의해 처음으로 설명되었으며 1970년대에 다니엘 샹크스에 의해 독립적으로 재발견되어 그의 이름을 따서 토넬리-샹크스(Tonel...

문제 Quadratic Residues에서 우리는 제곱근 모듈로 정수를 취하는 것이 무엇을 의미하는지 배웠습니다. 또한 제곱근을 구하는 것이 항상 가능한 것은 아니라는 것도 알았습니다. 앞의 경우 p = 29일 때는 제곱근을 계산하는 가장 간단한 방법도 충분히 빨랐지만, p가커질수록 이 방법은 매우 어려워집니다. 다행히도 Legendre 덕분에 ...

문제 우리는 모듈러 산술에서의 곱셈과 나눗셈을 살펴봤지만, 정수에 대한 모듈러 제곱근을 취하는 것은 무엇을 의미할까요? 아래 문제에서는 p = 29에 대해 작업합니다. 우리는 정수 a = 11을 가져와서 a² = 5 mod 29를 계산할 수 있습니다. a = 11이므로, a² = 5이고, 우리는 5의 제곱근을 11이라고 말합니다. 이것은 좋은 ...

문제 우리는 유한체가 더하거나 곱해도 항상 Fp 유한체의 다른 요소임을 알 수 있었다. 유한체의 모든 요소 g는 g * d ≡ 1 (mod p)를 만족하는 d를 가진다. 이를 g의 곱셈역라고 한다. 예를 들어 7 * 8 = 56 ≡ 1 (mod 11) 이다. 그렇다면 3 * d ≡ 1 (mod 13) 을 만족하는 곱셈역는 무엇인가? 페...

문제 우리는 지난 도전에서 선택하고 모듈러스 p를 선택했다고 상상하고 p가 소수인 경우로 제한할 것입니다. 정수 모듈로 p는 Fp로 표시된 필드를 정의합니다. 만약 모듈러가 소수가 아니라면, 정수 모듈러 n 집합은 환(ring)을 형성합니다 유한체 Fp는 정수 {0,1…,p−1}의 집합이며, 덧셈과 곱셈 모두에서 a+b=0, a×b=1과 ...

문제 당신이 몸을 숙이고 암호학자의 노트를 본다고 상상해보라. 여백에 다음과 같은 참고 사항이 표기되어 있는 게 보인다. 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 처음엔 그들이 미쳤다고 생각할지도 모른다. 이것이 오늘날 많은 데이터유출의 이유라고 생각될 수도 있겠지만, 이것은 모듈러 12에 대한 모듈러 연산에 지나지 않는다. (비...

개념 유클리드 알고리즘이 a, b의 최대공약수 GCD(a, b)를 구하는 알고리즘이었다면 확장 유클리드 알고리즘은 a * s + b * t = GCD(a, b)를 만족하게 하는 정수 s, t를 구하는 알고리즘이다. 초기 값은 s1, s2 = 1, 0 t1, t2 = 0, 1 로 세팅해줍니다. 초기값을 세팅하는 이유 초기값 0,1 s와 t를...