~ RSA의 모든 연산 모든 문제에는 모듈러 지수화 ( 나머지 연산 ) 을 사용하게 된다 ~
mod는 나머지 연산자이다
10 mod 3이면 10%3과 같은건데 쉽게 다시 말하면
나머지가 3보다 작을때까지 계속 뺀다고 생각하면 된다
10 - 3 = 7
7 - 3 = 4
4 - 3 = 1
결국 답은 1이되는것이다
실제로, 10%3 하면 몫은 3 나머지는 1이 나오게 된다
% = mod
다시 문제로 돌아와서
101¹⁷ mod 22663 을 구하라고 했는데 거듭제곱과 나머지연산자를 한번에 수행해주는
pow 함수를 사용할 것이다
result = pow(2, 3) # 2의 3승인 8을 계산합니다.
print(result) # 출력: 8
result_with_modulus = pow(2, 3, 5) # (2의 3승)을 5로 나눈 나머지를 계산합니다. 결과는 3입니다.
print(result_with_modulus) # 출력: 3
pow ( base,exponent,modulus )
이런 식의 함수인데 설명하자면 이렇다
base: 거듭 제곱할 밑 숫자
exponent: 밑을 거듭 제곱할 지수
modulus (선택적): 제공된 경우, 결과는 해당 모듈러 값으로 나눈 나머지로 계산
문제를 말로 풀면
1. 101의 17을 제곱하고 그 값을 22663을 22663보다 작은 값이 나올때까지 빼준다
2. 101의 17을 제곱하고 그 값을 22663으로 나머지연산을해 나머지를 구한다
같은 말이다
print(pow(101,17,22663))
코드로 표현해보면 이런식으로 나오게된다
= 19906
'Cryptography' 카테고리의 다른 글
[Cryptohack] RSA starter 3 write up (0) | 2023.08.31 |
---|---|
[Cryptohack] RSA starter 2 write up (0) | 2023.08.29 |
교내 해킹방어대회 문제 출제 (2) | 2023.07.12 |
Hxd와 xor 을 이용한 간단한 문제 만들기 (0) | 2023.07.11 |
[Cryptohack] Favourite byte Writeup (1) | 2023.06.23 |