Wargame/Cryptohack

Encoding Challenge

1. intro 코딩이 조금 귀찮긴 했지만 재밋는 문제였다. 2. code 및 분석 2.1. code #!/usr/bin/env python3 from Crypto.Util.number import bytes_to_long, long_to_bytes from utils import listener # this is cryptohack's server-side module and not part of python import base64 import codecs import random FLAG = "crypto{????????????????????}" ENCODINGS = [ "base64", "hex", "rot13", "bigint", "utf-8", ] with open('/usr/share/dic..

Network Attacks

1. intro 2. code 및 분석 2.1. code #!/usr/bin/env python3 import telnetlib import json HOST = "socket.cryptohack.org" PORT = 11112 tn = telnetlib.Telnet(HOST, PORT) def readline(): return tn.read_until(b"\n") def json_recv(): line = readline() return json.loads(line.decode()) def json_send(hsh): request = json.dumps(hsh).encode() tn.write(request) print(readline()) print(readline()) print(readline(..

Legendre Symbol

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 앞선 케이스에서 p가 29라면 쉽게 계산할 수 있었지만, p가 매우 크다면 터무니 없는 방법이 된다. 하지만 쉽게 제곱 잉여인지 아닌지 계산할 수 있는 방법이 르장드르 기호를 이용하는 방법이다. 르장드르 기호는 앞선 포스팅과 같이 1 or -1인지만 확인하면 된다. 2023.02.09 - [Tips & theory] - Legendre Symbol - 르장드르 기호 Legendre Symbol - 르장드르 기호 서론 지금까지 이런 해킹은 없었다. 이것은 크립토인가 수학인가. 이론 앞서 공부한 제곱 잉여 x^2 = a mod p 에서 p가 충분히 작다면 쉽게 a를 구할 수 있었지만, p가 커지면 어떻게 제곱 잉여인지 wyv3rn..

Quadratic Residues

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 나머지 계산에서 곱셈과 나눗셈에 대해서 알아보았지만, 나머지를 제곱근으로 표현하는 것이 무엇을 의미할까. p = 29라고 가정해보자. a^2 = 5 mod 29를 계산해보면 a는 11이 됨을 알 수 있다. (앞서 작성한 코드를 조금 수정해서 사용) ┌──(kali㉿kali)-[~/Downloads] └─$ python solve.py 29 ['1 : 1', '2 : 4', '3 : 9', '4 : 16', '5 : 25', '6 : 7', '7 : 20', '8 : 6', '9 : 23', '10 : 13', '11 : 5', '12 : 28', '13 : 24', '14 : 22'] 그러므로 11은 5의 제곱근이라고 할 수 ..

Modular Inverting

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 역함수다! 우리는 유한체가 더하거나 곱해도 항상 Fp 유한체의 다른 요소임을 알 수 있었다. 유한체의 모든 요소 g는 g * d ≡ 1 (mod p)를 만족하는 d를 가진다. 이를 g의 곱셈역라고 한다. 예를 들어 7 * 8 = 56 ≡ 1 (mod 11) 이다. 그렇다면 3 * d ≡ 1 (mod 13) 을 만족하는 곱셈역는 무엇인가? 페르마의 소정리가 어떻게 곱셈역을 구하는데 도움이 되는지 생각해보자. 3. exploit 3.1. 페르마의 소정리 활용 페르마의 소정리는 앞서 공부한 것과 같이 p가 소수면 a^(p - 1) mod p = 1 이는 곧 a^(p - 1) mod p = 1 mod p a^(p - 1) * p^(-..

Modular Arithmetic 2

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 해석이다. p가 소수일때 Fp를 {0,1,2,...,p-1} 의 유한체라고 하자. 이때 각 요소를 a라고 가정하면, 이 a의 덧셈역과 곱셈역이 존재하며 앞서 공부한 것과 같이 a + b = 0, ab = 1 는 항상 존재한다. 이제 p를 17이라고 가정하고 3^17 mod 17과 5^17 mod 17을 계산해보자. 아래와 같이 간단히 나머지만 출력하도록 코딩해보았고 a = b = 3 c = [] d = [] x = 18 n = 17 for i in range(1,x): c.append(str(a % n).rjust(2,' ')) a = a * b a = b = 5 for i in range(1,x): d.append(str(a..

Modular Arithmetic 1

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 문제를 간단히 해석해보자. 아래와 같은 노트가 적힌 것을 보면 미쳤다고 생각할지 모르지만, 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 이것은 12로 나눈 모듈러 산술이다. 당신은 이것을 모듈러 산술이라고 부르지 않았을지도 모르지만, 당신은 시간을 말하는 것에 대해 배우고나서 이런 종류의 계산을 해오고 있다. 정석으로 이야기하자면 이 두 정수를 m의 합동 모듈이라고 하고 a ≡ b mod m 이라고 표현한다. 이를 달리 표현하면, a를 m으로 나눴을때 나머지는 b라는 것과 같고, 만일 m으로 a를 나누면 0이 된다는 것과 같다. a ≡ 0 mod m 이 때 아래 중 작은 값을 구하라. 11 ≡ x mod 6 8146..

Extended GCD

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 확장된 유클리드 호제법을 설명하는 문제이다. 결국 p * u + q * v = gcd(p,q) 의 공식을 만족하는 u와 v 중 최소값을 찾는 문제이다. 아래 포스팅과 같이 소스코드를 작성해보았고, 이를 적용하였다. 2023.02.02 - [Tips & theory] - Expanded Euclid's Algorithm - 확장된 유클리드 호제법. Expanded Euclid's Algorithm - 확장된 유클리드 호제법. 서론 아직은 이걸 왜 알아야하는지 모르겠지만 일단 하는 공부 ㅋ 확장 유클리드 호제법 공식을 처음 봤을때 최소공배수인가라는 생각을 했고, 퇴근하며 운전하는 동안 머릿속으로 알고리즘을 wyv3rn.tistor..

Greatest Common Divisor

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 최대공약수 즉 GCD를 구하는 문제이다. 이는 유클리드 호제법을 통해 쉽게 구할 수 있으며, 아래 링크와 같이 직접 만들어보았다. 2023.02.01 - [Tips & theory] - Euclidean algorithm - 유클리드 호제법 Euclidean algorithm - 유클리드 호제법 서론 크.... 내가 유클리드 호제법에 대해서 포스팅하는 날이 올줄이야... 상상도 못했다 ㅋㅋㅋ 이론 임의의 두 정수가 있을 때 두 정수의 최대공약수를 구하는 방법 중 하나가 유클리드 호제법 wyv3rn.tistory.com 3. exploit a = int(input()) b = int(input()) while 1: if a < ..

You either know, XOR you don't

1. intro 2. code 및 분석 2.1. code N/A 2.2. 분석 이제부터 시작인가보다. 힌트로는 역시 flag 형식을 생각해보라고 한다. 우선 해당 문자열을 byte 값으로 바꾸고, xor로 0부터 0xff까지 연산하면서 첫 문자가 c 일 때를 출력해보았다. e = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104') d = '' for i in range(0xff): for j in range(len(e)): d += chr(e[j] ^ i) if d[0] == 'c': print(hex(i), d) d = '' ┌──(kali㉿kali)-[~/Downloads..