Quadratic Residues

728x90

1. intro

2. code 및 분석

2.1. code

N/A

2.2. 분석

나머지 계산에서 곱셈과 나눗셈에 대해서 알아보았지만, 나머지를 제곱근으로 표현하는 것이 무엇을 의미할까.

p = 29라고 가정해보자.

a^2 = 5 mod 29를 계산해보면 a는 11이 됨을 알 수 있다.

(앞서 작성한 코드를 조금 수정해서 사용)

┌──(kali㉿kali)-[~/Downloads]
└─$ python solve.py
29
['1 : 1', '2 : 4', '3 : 9', '4 : 16', '5 : 25', '6 : 7', '7 : 20', '8 : 6', '9 : 23', '10 : 13', '11 : 5', '12 : 28', '13 : 24', '14 : 22']

그러므로 11은 5의 제곱근이라고 할 수 있고

a = 11 , a^2 = 5

라 표현할 수 있다.

이제 제곱근이 18인 경우에 대해서 알아보자.

우리는 이것을 찾기 위해 a = 1부터 a = p-1까지 계산해볼 것이다.

만일 제대로 코딩되었다면 a^2 = 18이 되는 a 값을 찾을 수 없을 것이다.

이렇게 제곱근이 존재하면 제곱 잉여, 존재하지 않으면 비제곱 잉여라고 한다.

문제에서, p = 29이고 a가 14, 6, 11일 때 둘은 비제곱 잉여, 하나는 제곱 잉여다.

여기서 제곱 잉여를 찾고, 최소 값이 flag이다.

3. exploit

앞서 작성한 코드를 적용해보면

n = int(input())
a = []

for i in range(1,(1+n)//2,1):
    a.append((i**2)%n)

print(a)

┌──(kali㉿kali)-[~/Downloads]
└─$ python solve.py
29
[1, 4, 9, 16, 25, 7, 20, 6, 23, 13, 5, 28, 24, 22]

가 되고, 해당하는 것은 6 밖에 없다.

이는 8번째 값이므로 제곱 잉여는 8 또는 -8이 된다.

최솟값이라고 해서 -8일 줄 알았는데 그냥 8을 넣었더니 풀림 ㅋ