[Cryptohack] RSA (RSA STARTER 1, 2, 3)

RSA STARTER1

문제 및 설명

RSA의 모든 작업에는 모듈식 지수화가 포함됩니다. 모듈식 지수화는 암호학에서 광범위하게 사용되는 연산이며 일반적으로 다음과 같이 작성된다: 2^10 mod 17 이것은 어떤 수를 특정 거듭제곱(2^10 = 1024)으로 올리고 나머지 수를 다른 수만큼 취하는 것이라고 생각할 수 있다(1024 mod 17 = 4). 파이썬에는 이 작업을 수행하기 위한 기본 연산자가 있습니다: pow(기본, 지수, 계수) RSA에서 모듈식 지수화는 프라임 팩터화 문제와 함께 "트랩도어 기능"을 구축하는 데 도움이 됩니다. 이것은 한 방향으로 계산하기는 쉽지만, 올바른 정보가 없으면 역으로 계산하기가 어려운 함수이다. 그것은 우리가 메시지를 암호화할 수 있게 해주고, 오직 키를 가진 사람만이 그것을 해독하기 위해 역작업을 수행할 수 있다. 101^17 mod 22663에 대한 해결책을 찾으십시오

풀이

answer = (101, 17, 22663)
print(anwser)

답은 19906이다.

RSA STARTER2

문제 및 설명

RSA 암호화는 일반적으로 두 소수의 곱인 지수와 계수 N을 가진 메시지의 모듈식 지수입니다: N = p * q. 지수와 계수는 함께 RSA "공개 키"(N, e)를 형성합니다. e에 대한 가장 일반적인 값은 0x10001 또는 65537입니다. 지수 = 65537, 소수 p = 17, q = 23을 사용하여 숫자 12를 "암호화"합니다. 당신은 암호문으로 어떤 숫자를 얻나요?

풀이

b = 12 
e = 65537
p = 17
q = 23
n = p*q

answer = pow(b, e, n)
print(answer)

답은 301이다.

RSA STARTER 3

문제 및 설명

RSA는 계수 N의 인수분해의 어려움에 의존한다. 소수가 발견될 수 있다면 우리는 N의 오일러 피 함수로 계산하여 암호문을 해독할 수 있다. 주어진 N = p*q 및 두 소수: p = 8575040833397127524899993810777 q = 1029224947942998075080348647219 N의 합계는 얼마입니까?

풀이

 둘은 소수이기때문에 오일러의 피함수에선 p, q는 p-1, q-1를 통해 계산을 해보았다.

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
answer = (p-1)*(q-1)
print(answer)

답은 882564595536224140639625987657529300394956519977044270821168이다.