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{}

Cryptohack 에서 제일 안되는 부분이
XOR 개념이였기 때문에 따로 정리를 할것이다
그리고 부족했던 ascii 개념을 더 정리해보자면 

                                           ASCII 코드표

ascii 코드 = 7bit 
영문 알파벳을 사용하는 대표적인 문자 인코딩이다 
chr() ord()
chr 함수는 ascii숫자를 대응하는 문자로 바꿔주고 
ord 는 문자를 ascii 값으로 변환해주는거임

print(type(chr(99)))

print(chr(99) == "c")

print(99 == ord("c"))

99를 ascii 코드에 대응하게 chr 을 써서 문자 "C" 로 바꾸었으니까 <class 'str'>
같은이유로 TRUE
C를 다시 ord를 사용해 ascii 코드로 변환시키면 99이니까  TRUE

# Favourite byte

For the next few challenges, you'll use what you've just learned to solve some more XOR puzzles.
I've hidden some data using XOR with a single byte, but that byte is a secret. Don't forget to decode from hex first.
73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d

다음 몇 가지 챌린지에서는 방금 배운 것을 사용하여 더 많은 XOR 퍼즐을 풀게 됩니다.
단일 바이트로 XOR을 사용하여 일부 데이터를 숨겼지만 해당 바이트는 비밀입니다. 
먼저 16진수에서 디코딩하는 것을 잊지 마십시오.

일단 문제를 먼저 바이트 형태로 바꿔서 디코딩을 해준뒤 
모든 경우의 수를 찾아 무차별적으로 1btyes에 xor 을 각각해줌으로써 플래그값을 알아낼 것이다.

from Crypto.Util.number import *
fl = bytes.fromhex("73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d")

for i in range(256):
    for char in fl:
        print(chr(char ^ i), end="")
    print()

계속 증가하는 변수인 i를 1bytes에 경우의 수를 다 넣는 것인데 
이때 1bytes = 8bit
1bit = 0과1을 나타내기 때문에 2⁸ = 256을 대응하는것이다.
그럼 char이라는 변수 안에 문제를 넣고 문제와 증가하는 변수 i를 xor 시켜서 chr 함수로 문자로 나오게 해보면

Þ
ß
Þ
±
ß
Û
± ....

이런식으로 나오기 때문에 end 함수를 써주면 많은 결과값중에 

nelhsg,d-,C-)CqeCz(j,in-+/C~e+ya
~odmirf-e,-B,(BpdB{)k-ho,*.Bd*x`
}lgnjqe.f/.A/+AsgAx*h.kl/)-A|g){c
|mfokpd/g./@.*@rf@y+i/jm.(,@}f(zb
crypto{0x10_15_my_f4v0ur173_by7e}
bsxqunz1y01^04^lx^g5w1ts062^cx6d|

이렇게 플래그를 찾을 수 있다 하지만
플래그만 딱 출력 하는, 더 좋은 코드를 짤 수 있는데  if 문을 사용해서
문제 첫글자, 1byte가 flag 포맷일때만 출력이 되게끔 코드를 짜보겠다 

from Crypto.Util.number import *
fl = bytes.fromhex("73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d")

for i in range(256):
    if fl[0] ^ i == ord("c"):
        for char in fl:
            print(chr(char ^ i),end="")

이 문제에서 flag 포맷은 crypto{}
만약 fl 변수의 0번째 i랑 xor 했을때가 c 일때만 다음 for문으로 넘어가게끔 코드를 짠것이다.
이때 C는 ord 함수를 사용해서 ascii 코드로 변환해 조건문을 작성해준다. 
만약 조건문이 성립이 되지않는다면 다음 for문으로 안넘어가기 때문에 결국 print 까지도달을 안해서 아무것도 출력이 되지 않을것이다.
crypto{0x10_15_my_f4v0ur173_by7e}
그럼  flag만 뽑아서 출력 해 줄 수 있다
flag 포맷을 잘이용하면 된다는 사실을 알았다.. 이 경험으로 ,, flag 포맷에 대한 설명도 세미콜론때  나름 잘했다 ㅋㅋㅋ

# SingleByteXor

dramhack에 비슷한 예제가 있다 

똑같이 단일 바이트라는 점을 이용해서 작성하면 된다 

from Crypto.Util.number import*

fl = bytes.fromhex("54586b6458754f7b215c7c75424f21634f744275517d6d")

for i in range(256):
    if fl[0] ^ i == ord("D"):
        for ch in fl:
            print(chr(ch ^ i), end="")

문제를 빼다 박아 놓은 수준으로 똑같이 풀었다 flag 포맷은 다르니까 그 점만 다른걸 제외하면 코드는 똑같다.
DH{tHe_k1LleR_1s_dReAm} 

글을 마치며 

xor 개념 자체도 나름 이해한거 같고 ascii에 대한 이해는 확실하게 되었다

 C+F 해서 flag 값을 찾아도 되는데 더 완벽한 코드를 짤 순 없을까 하면서 고민해보고 

이것저것 시도하는 과정이 나름 재미있었다 이런 경험으로 

코드작성할때 이거에는 이 함수 써야지, 이렇게 해야지 이런 생각 범위가 처음보다 확실히 늘어난거 같다 

Basic_Crypto1

This Problem Basic_Crpyto(Roman emperor’s cipher)

FLAG FORMAT(A~Z) and empty is “_”

DH{decode_Text}

txt 폴더안에 

EDVLF FUBSWR GUHDPKDFN 

이렇게 적혀 있는거 보고 카이사르 암호문인걸 알았다 

caesar decoder라고 구글링을 해서 dcode 사이트에 돌렸더니 

https://www.dcode.fr/caesar-cipher

BASIC CRYPTO DREAMHACK

이 형식으로 나와서 문제에서 말한 플래그 형식으로 넣었음

DH{BASIC_CRYPTO_ DREAMHACK}