Like Goseungduk

#sexy소수 #sexyRSA #SECCON2021 SECCON 2021 SPEEDRUN 챌린지에 출제된 sexyRSA 문제이다. n = 0xe72988e811f04091c3291ac28f1e8332193187f3dc5af01579c36badb06671aa9a9543aa07eba8cdab36d787f1ff98a06db995c43cd5c63581ce050e0b9ba856634dabfaf8c7f271fbd026edd6ea1257b16013a526e0581a688cc6a335e7ee4c1b0633f0532d3d0824824195b6b249c70cf0e458609efc01a6575f084e6de53b e = 0x10001 c = 0x6fadd5d7095bd6f45de69bb4e76080e0ea5f8c5a159d..

RSA 암호화 RSA는 공개키 암호화 방식중 하나이다. 우선, 암호화 하는데에 KEY가 필요하겠다. 키는 총 두 가지의 KEY가 관여하는데 하나는 공개키, 하나는 개인키(비밀키)이다. 먼저 이 KEY들이 어떻게 만들어지는지 보자. 1. KEY 우선 공개키. 임의의 서로소인 수 p, q를 정하자. 그리고 n = p * q Φ(n) = (p-1) * (q-1)이라 하자. (Φ는 "파이" 라고 읽으면 된다) 그리고 1 < e < Φ(n) 이면서 Φ(n)과 서로소인 e를 정한다. 여기까지 잘했다면 공개키는 두 수 n과 e의 조합인 로 정할 수 있다. 다음은 개인키. 여기서 이전에 설명했던 모듈러 연산 및 역원이 쓰이는데 공개키 e와 곱해져서서 Φ(n)으로 나눴을 때 나머지가 1이 되는 d가 개인키에 이용된다. ..

모듈러 연산 모듈러 연산은 간단히 말하면 나머지를 구하는 연산이라고 볼 수 있다. 위 식에서 a는 피제수, b는 제수, c는 나머지 이다. 예를 들면, 26 mod 5 = 1 이 될 수 있을 것이다. 이해 되었다면 이제 모듈러 연산의 여러 특징을 정리하려 한다. 1. 합동 모듈러 연산에서 26 mod 5 나 36 mod 5 는 모두 똑같이 1로 같다. 이를 합동 이라는 개념으로 부를 수 있으며 표현은 이와 같이 한다. 1 ≡ 6 ≡ 26 ≡ 36 mod 5 = 1 2. 성질 모듈러 연산에는 아래와 같이 좌변의 덧셈과 곱셈에 대해 분해할 수 있는 성질이 있다. [1] (a + b) ≡ ((a mod n) + (b mod n)) mod n [2] (a * b) ≡ ((a mod n) * (b mod n)) ..

1. 유클리드 알고리즘 유클리드 알고리즘은 최대 공약수의 두 가지 성질에 기반한 두 수의 최대공약수 추출 알고리즘이다. gcd(a,0) = a 두 수 중에서 한 쪽이 0이라면 두 수의 최대공약수는 다른 한 쪽 수이다. gcd(a,b) = gcd(b,r) ( ※ r은 a를 b로 나눈 나머지이다. ) 위와 같은 성질을 통해 나온 유클리드 알고리즘은 다음과 같다. gcd(a,b) = gcd(b,r) = ... = gcd(r,0) = r 이에 대한 것은 예제로 알아보자. ex) gcd(48,15) = gcd(15,3) = gcd(3,0) = 3 이런 식으로 48과 15의 최대공약수를 구할 수 있다. 파이썬으로 유클리드 알고리즘을 짜보자. def gcd(a,b): if(b==0): return a return g..