[CryptoHack] RSA Starter 1

 

설명

---

RSA의 모든 작업에는 모듈러 지수가 포함된다.

 

모듈러 지수는 암호화에서 광범위하게 사용되는 연산이며, 일만적으로 다음과 같이 작성된다. $2^{10} \bmod 17$

 

어떤 숫자를 특정 거듭제곱($2^{10} = 1024$)로 올린 다음 나머지를 다른 숫자 ($1024 \bmod 17 \equiv 4$)로 나누는 것으로 생각할 수 있다.

파이썬에는 이 연산을 수행하기 위한 내장 연산자가 있다. pow(base, exponent, modulus)

 

RSA에서 모듈러 지수화는 소인수분해 문제(IFP)와 함께 "트랩도어 기능" 을 구축하는데 도움이 된다. 이것은 한 방향으로 계산하기는 쉽지만, 올바른 정보가 없으면 역방향으로 계산하기 어려운 함수이다. 이를 통해 메시지를 암호화할 수 있으며 키를 가진 사람만 역 작업을 수행하여 암호를 해독할 수 있다.

 

$101^{17} \bmod 22663$을 찾아라.

 

풀이

---

print (pow(101, 17, 22663))