RSA ctf 문제풀거나 할때 유용하게 쓰이는 소인수분해 툴인데 

엄청큰 수를 입력하면 소인수분해가 되는것을 확인할수있는데, 그 옆에 있는 알파벳의 뜻을 정리하려고한다.

입력한 번호가 현재 데이터베이스에 어떻게 나열되어 있는지를 나타냄.
C   : 복합, 알려진 요인 없음
CF : 복합재, 알려진 요인
FF : 합성, 완전 인수분해
P : 확실한 소수 
Prp : 아마도 소수일 것 
U : 알 수 없음
Unit :"1"만을 위한 단위
N : 이 번호는 데이터베이스에 없다(귀하의 설정으로 인해 추가되지 않았다).
* : 이 요청 중에 데이터베이스에 추가됨

한마디로 fatordb에 내가 입력한 수가 소인수분해가 잘되는지 Db에는있는지 볼수있는 알파벳인거

대부분 문제 풀면 FF가 뜨면서factorize 되는걸 볼수있음 

보안관제 동아리에서 중학생들을 대상으로 문제를 출제했다.

1# Hiscon 25point
Olssv dlsjvtl av ohuzlp! obtt.. kv fvb ruvd aol huzdly av aopz alza?
OZVJ{K0_f0b_ruVd_c1nLUly}
*hint = title

 
25점 문제로 고전암호학 vigenere를 출제했다 
플래그 포맷을HSOC 랑 대조해봤을때 "O"가 H를 가리키기도 하고 V를 가르키기도 하기 때문에 쉬프트하는 카이사르가 아니라 비즈네르라고 유추할수 있다 
 
문제의 키 값은 Hiscon 의 H이다 툴이나 코드를 사용해 복호화를 하면 
HSOC{D0_y0u_knOw_v1gENere} 라는 flag 값이 나오게 된다 
 

2# RShelter..A 100point
핵 전쟁으로 방공호에 갇혀있는 돌로레스는 문밖에 암호가 적혀진 메모를 발견했다 누가 장난을 치고 간것인지... 알수없는것 투성이다.

제목에도 힌트가 있지만 “암호를 푸는데뎌 얼마나 걸릴지도 모르고, 시간낭비일지도 모른다” 라는 내용으로 유추해보면 큰 수일수록 소인수분해가 어렵다는 점을 이용한 암호알고리즘인 Rsa 암호 문제인걸 알수있다 그점을 고려해서
문제 폴더에 있는 output 메모를 열면

n = 123540945535348818505443663552430339730797994651078703869158434458801148680536748800954485191293084838693867539898129034405126458533526245941520570951570457825948733919413051950775476499203976292917331256051251396841673467230808003266709856927506305902342904853542480412988326456097416341155911411158224483331   
e = 3
ct = 4195958341811449247679798367896069015351823066643635550381426047270427958450169559723963889837872491377599837640886837868076438894848613


e값이 3으로 너무 작은 소수이기 때문에 이 점을 이용하여, 낮은 지수 공격을 통해

from gmpy2 import iroot, local_context

c = 4195958341811449247679798367896069015351823066643635550381426047270427958450169559723963889837872491377599837640886837868076438894848613

with local_context() as ctx:
    ctx.precision = 3000
    m = iroot(c,3)[0]
   
    print(bytes.fromhex('%x' % int(m)))

 
이런식으로 코드를 작성해 flag 값을 얻어낼수도 있고 , RSActf tool을 이용해 알아낼수도 있다 
HSOC{1@Mv3ryBoring} 기껏 복호화 해놨더니 난 지루하다는 뜻이다..ㅋㅋ
 

지금 까지 했었던 rsa starter을 총 동원해서 이번엔 진짜 암호문을 풀어보겠다 

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
n = q*p
phi = (q-1)*(p-1)
d = pow(e,-1,phi)
c = 77578995801157823671636298847186723593814843845525223303932
flag = print(pow(c,d,n))

= 13371337

http://factordb.com/

개인키 d를 구하는 것이다 

개인키 d 는 inverse(e,phi)또는 pow(e,-1,phi)

from Crypto.Util.number import *
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(d)

= 121832886702415731577073962957377780195510499965398469843281

p = 충분히 큰 소수
q = 충분히 큰 소수
N = p * q
e = 65537

발견된 가장 큰 2의 소수이면서 phi랑 서로소이면서 페르마소수중에 가장 큰 소수

3가지의 조건을 성립하는 대중적인 공개키 

소인수 분해가 안될수록 RSA의 의미가 있으므로 쓰는걸로 추정.. 해외 사이트뒤져봐도 왜 저 조건을 성립하는 소수를 공개키의 일부로 주로 쓰게 되는지 모르겠다 

=>라고 작성했었는데 애초에 조건자체가 틀렸다 

페르마 소수라는것은 페르마가 소수를 구하는 법을 설명한것인데 

 [ Fn = 2²ⁿ + 1 ] 다음 공식을 가지는 수를 페르마 수 (Fermat number) 이라고 한다 

이를 통해 증명을 할 수 있다.

F0=3

F1=5

F2=17

F3=257

F4=65537

F5=4294967297=641x6700417 (즉 F5 는 소수가 아니다)

페르마는 F4보다 큰 어떤 수에 대해서도 소수라는 것을 증명하지 않았고,

F24 까지 수를 살펴본다면 많은 수가 합성수라는것이 알려졌다.

자 그럼 의문점이 생길건데 왜 RSA 비대칭키 암호문에 공개키를 가장큰 소수를 사용하는것일까? 

e값은 큰소수를 가지고 있어야 보안성이 높아지는데 65537은 작은 소인수를 가지지 않는 큰 소수이고 작은 소수 2와 3을 기반으로 하여 만들어진 소수 이기 때문에 e값을 65537로 설정하면 암호화 복호화 과정에서 빠른 계산을 제공하기 때문에 1과 자기 자신을 제외하고 다른수로는 나누어지지 않는 65537이 선택된 것이라고 한다

.

.

.

그렇게해서 
공개키 <e, N> 이 만들어진다 

phi = (p - 1) * (q - 1) (오일러의 피함수)

d = pow(e, -1, phi)

또는 d = inverse(e,phi) (개인키 구하기)
<d, N>(개인키)

pt = 암호화할 데이터 = 평문 (plaintext)
ct (ciphertext) = pow(pt, e, N)  (암호문) 공개키를 넣어 암호문을 만들고 

암호문이된 ct를 
pow(ct, d, N) (복호화) 암호문에 개인키를 넣어 복호화를 시킨다 

이런식으로 RSA 알고리즘이 동작한다.

여기서 N은p*q를 구하라는 것이 아니라,

totient of N = 오일러의 피함수 N을 구하라는것이다 

오일러의 함수는 phi 라고 하는데 

개인키를 구할 때 

개인키 d는 inverse(e,phi) or pow(e,-1,phi) 로 phi를 사용해서 개인키를 구하게 된다

또, 개인키는 복호화 시킬때 pow(ct,d,n) 으로 사용하게 된다

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

= 882564595536224140639625987657529300394956519977044270821168

RSA에서 공개키를 만드는 방법은 이렇다 

1.두 개의 큰 소수(p, q) 선택.
2.n = p * q 계산.
3.φ(n) = (p - 1) * (q - 1) 계산.
4.작은 소수 e 선택 (일반적으로 65537).
5.e에 대한 φ(n)의 역원을 찾아 개인키 d 계산.
6.공개키: (n, e), 개인키: (n, d) 생성됨.

이 일련의 과정을 통해 암호문을 구할 수 있다 

text = 12
p = 17
q = 23
n = p * q
e = 65537
print(pow(text,e,n))

암호화 하려는 평문과 정해져있는 공개키중 하나인 E를 제곱 한 뒤 

N, 주어진 두 소수 q,p의 곱으로 모듈러스 지수화 ( 나머지연산 ) 을 해주면 값이 나오게 된다 

 = 301

~ 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

어느날, 고먐미의 초상화가 이상해졌다
누군가 임의로 초상화를 바꿔놓은것이다

범인이 남기고 간 유일한 단서는 ,

이사진속에 단일바이트와 XOR해서 만들어진 암호를 심어놨다는 단서 뿐.
과연 고먐미 초상화 사건의 범인을 찾을 수 있을 것인가…!
flag format: hsoc{}