Armory 문제(및 설명) Shamir의 스키마를 개선하여 결정론적으로 파생된 공유를 사용했습니다. 비트코인 개인 키 및 기타 비밀 데이터 저장에 좋습니다. 당신은 첫 번째 공유만 가지고 있고 플래그를 해제하기 위해 3개가 필요하기 때문에 어떤 가능성도 없습니다. 풀이 더보기 #!/usr/bin/env python3 import hashlib FLAG = b"crypto{???????????????????????}" PRIME = 77793805322526801978326005188088213205424384389488111175220421173086192558047 def _eval_at(poly, x, prime): accum = 0 for coeff in reversed(poly): accum *..

Bit by Bit 문제(및 설명) 당신이 ElGamal에 대해 들었는데, 이것은 몇 가지 멋진 특성을 가지고 있다고 들었습니다. 저는 모든 비트를 다른 비밀로 암호화했으므로 당신은 제 플래그값을 복구할 수 못합니다. 풀이 더보기 from Crypto.Random import random from Crypto.Util.number import getPrime, bytes_to_long FLAG = b'crypto{??????????????????????????????????????????}' def get_padding(): seed = 256 e = random.randint(2, q) padding = pow(seed, e, q) return padding def public_key(): x = ra..

Find the Lattice 문제(및 설명) 보안 시스템에 대한 트랩도어 함수를 형성할 수 있는 어려운 문제를 포함하는 것으로 알려진 격자(lattices)를 살펴보았습니다. 또한, 암호 해독(cryptanalysis)에서는 격자가 격자와 관련이 없는 것처럼 보이는 암호 프로토콜을 깰 수 있습니다. 이 도전 과제는 플래그를 암호화하기 위해 모듈러 산술을 사용하지만, 프로토콜 내에는 2차원 격자가 숨겨져 있습니다. 이 도전에 시간을 투자하고 어떻게 격자를 사용하여 이를 깰 수 있는지 찾는 것을 강력히 권장합니다. 이것은 많은 자료가 있는 유명한 예제이지만, 시스템 내에서 격자를 찾아내는 것이 종종 깨는 핵심이 됩니다. 힌트로는 이 도전을 이전 도전에서 다룬 가우스 소거법(Gaussian reduction..

Gram Schmidt 문제(및 설명) 지난 문제(Size and Basis)에서 우리는 직교 기저(orthogonal basis)라고 하는 특별한 종류의 기저가 있다는 것을 보았습니다. 어떤 벡터 공간 V에 대한 기저 v1, v2, ..., vn이 주어졌을 때, 그램-슈미트(Gram-Schmidt) 알고리즘은 벡터 공간 V에 속하는 직교 기저 u1, u2, ..., un을 계산합니다. 제프리 홉스타인, 질 파이퍼, 조셉 H. 실버먼의 '수학적 암호학 입문' 책에서 그램-슈미트 알고리즘은 다음과 같이 주어집니다: 그램-슈미트 알고리즘 u1 = v1 반복 i = 2,3,...,n μij = vi ∙ uj / ||uj||^2, 1 ≤ j

Vectors 문제(및 설명) 먼저 격자를 정의하거나 암호학에서 격자가 어떻게 나타나는지에 대해 이야기하기 전에, 선형 대수의 기본 사항을 살펴보겠습니다. 다음 도전 과제들은 복습으로 간주되어야 하며, 만약 이것이 완전히 처음이라면 약간의 백그라운드 독서가 필요할 수 있습니다. 여전히 우리는 "수학적 암호학 입문" (Hoffstein, Pipher, Silverman) 및 격자 및 그 응용에 대한 이 훌륭한 소개를 추천합니다. 벡터 공간 V는 필드 F 위에서 정의된 집합으로, 두 개의 이항 연산자로 구성됩니다. 벡터 v ∈ V 및 스칼라 a ∈ F에 대해, 벡터 합은 두 개의 벡터를 가져와서 다른 벡터를 생성합니다: v + w = z, 여기서 v, w, z ∈ V 및 스칼라 곱은 벡터와 스칼라를 가져와서..

Gotta Go Fast 문제 저는 엔트로피가 고갈되는 것을 걱정할 필요가 없을 거에요. 이 새로운 스크립트로 영원히 OTP를 생성할 거예요! 풀이 더보기 더보기 #!/usr/bin/env python3 import time from Crypto.Util.number import long_to_bytes import hashlib from utils import listener FLAG = b'crypto{????????????????????}' def generate_key(): current_time = int(time.time()) key = long_to_bytes(current_time) return hashlib.sha256(key).digest() def encrypt(b): key = ge..

Collider 문제 입자 물리학에 관한 내 문서 시스템을 확인해보세요. 각 문서는 해시로 고유하게 참조됩니다. nc socket.cryptohack.org 13389 으로 접속하세요. 풀이 더보기 import hashlib from utils import listener FLAG = "crypto{???????????????????????????????????}" class Challenge(): def __init__(self): self.before_input = "Give me a document to store\n" self.documents = { "508dcc4dbe9113b15a1f971639b335bd": b"Particle physics (also known as high energy ..

Script Kiddie 문제 저는 Github에서 이 멋진 스크립트를 찾았고, 학교 Wi-Fi를 돌면서 듣고 있는 누구에게도 내 비밀을 지키기 위해 사용하고 있습니다! 풀이 더보기 from Crypto.Cipher import AES import hashlib import secrets def header(): print(""" _____ _ __ __ _ | __ \(_)/ _|/ _(_) | | | |_| |_| |_ _ ___ | | | | | _| _| |/ _ \ | |__| | | | | | | | __/ |_____/|_|_| |_| |_|\___| | | | | | | | | |__| | ___| | |_ __ ___ __ _ _ __ | __ |/ _ \ | | '_ ` _ \ / _`..

Diffie-Hellman Starter 3 문제 및 설명 디피-헬만 프로토콜은 이산 로그가 주어진 그룹에 대해 "어려운" 계산으로 가정되기 때문에 사용됩니다. 프로토콜의 첫 번째 단계는 소수 p와 유한체의 생성자 g를 설정하는 것입니다. 이러한 값은 특정한 경우에 이산 로그를 효율적인 알고리즘으로 해결할 수 있는 상황을 피하기 위해 신중하게 선택되어야 합니다. 예를 들어, p = 2*q +1과 같은 안전한 소수를 일반적으로 선택합니다. 여기서 p - 1의 인수는 {2,q}로, q는 다른 큰 소수입니다. 이렇게 함으로써 디피-헬만 프로토콜을 포홀리그-헬만 알고리즘으로부터 보호할 수 있습니다. 사용자는 그런 다음 비밀 정수 a < p를 선택하고 g^a mod p를 계산합니다. 이 값은 보안이 취약한 네트워..

Diffie-Hellman Starter 1 문제 및 설명 정수 모듈로 n으로 이루어진 집합은 덧셈과 곱셈의 연산을 포함하여 링(Ring)이 됩니다. 이는 집합 내의 두 요소를 더하거나 곱하는 경우에도 집합 내의 다른 요소가 반환된다는 것을 의미합니다. 모듈러스가 소수일 때: n = p인 경우, 우리는 집합 내의 모든 요소에 대한 역원을 보장받으며, 이로 인해 링은 필드(Field)로 승격됩니다. 이 필드를 유한체 Fp라고 합니다. Diffie-Hellman 프로토콜은 일반적으로 큰 소수인 유한체 Fp의 요소들로 작동합니다. 소수 p = 991과 요소 g = 209가 주어진 경우, g * d mod 991 = 1을 만족하는 역원 d를 찾아보겠습니다. 풀이 더보기 g * d mod 991 = 1에 대한 역..

Adrien's Signs 문제 Adrien은 심볼과 마이너스 기호를 이용하여 메시지를 암호화하는 방법을 고려하고 있습니다. 플래그를 복구하는 방법을 찾을 수 있을까요? 풀이 더보기 from random import randint a = 288260533169915 p = 1007621497415251 FLAG = b'crypto{????????????????????}' def encrypt_flag(flag): ciphertext = [] plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) for b in plaintext: e = randint(1, p) n = pow(a, e, p) if b == '1': ciphertext.append(n) els..

Modular Square Root 문제 및 설명 르장드르의 기호를 소개하면서, 소수에 대해 모듈로를 사용하여 제곱근이 있는지를 빠르게 판별하는 방법을 알아보았습니다. 더 나아가서, 이러한 제곱근을 효율적으로 계산하기 위한 알고리즘도 있습니다. 실제로 가장 좋은 알고리즘은 Tonelli-Shanks라고 불리며, 이는 19세기에 이탈리아인에 의해 처음으로 기술되었으며, 1970년대에 Daniel Shanks에 의해 독립적으로 재발견되었습니다. 2가 아닌 모든 소수는 p ≡ 1 mod 4 또는 p ≡ 3 mod 4 형태입니다. 왜냐하면 모든 홀수는 이러한 합동식을 따르기 때문입니다. 이전의 도전에서 암시한 대로, p ≡ 3 mod 4 경우에는 페르마의 소정리로부터 직접적으로 계산 가능한 매우 간단한 공식을 ..

Quadratic Residues 문제 및 설명 우리는 모듈로 산술에서 곱셈과 나눗셈을 살펴봤지만, 정수의 모듈로를 사용하여 제곱근을 취하는 것은 무엇을 의미할까요? 다음 논의를 위해 모듈로 p = 29에서 작업해 봅시다. 우리는 정수 a = 11을 가지고 a² = 5 (mod 29)를 계산할 수 있습니다. a = 11이므로, a² = 5이며, 우리는 5의 제곱근을 11이라고 말합니다. 이것은 좋아보이지만, 이제 18의 제곱근에 대해 생각해 봅시다. 위에서는 a² = 18인 정수 a를 찾아야 함을 알고 있습니다. 첫 번째 생각은 a = 1부터 a = p-1까지 반복하는 것일 것입니다. 이 논의에서 p는 크지 않으므로 빠르게 확인할 수 있습니다. 시도해보고, 이를 코딩하여 어떤 결과가 나오는지 확인해 보세..

CERTainly not 문제 및 설명 앞선 문제에서 언급한 대로, PEM은 DER로 인코딩된 ASN.1 위에 멋진 포장지입니다. 경우에 따라서는 DER 파일을 직접 만날 수 있습니다. 예를 들어, 많은 Windows 유틸리티는 기본적으로 DER 파일로 작업하는 것을 선호합니다. 그러나 다른 도구들은 PEM 형식을 기대하며 DER 파일을 가져오는 데 어려움을 겪을 수 있으므로 한 형식을 다른 형식으로 변환하는 방법을 알고 있는 것이 좋습니다. SSL 인증서는 현대 웹의 중요한 부분으로, 암호화 키를 조직에 대한 세부 정보와 결합시킵니다. TLS 카테고리에서 이에 대해 자세히 다룰 것입니다. 여기에 제시된 것은 DER로 인코딩된 x509 RSA 인증서입니다. 인증서의 모듈러스(modulus)를 찾아서, 답..

Modular Arithmetic 1 문제 및 설명 몸을 숙이고 암호학자의 노트를 본다고 상상해 보세요. 다음과 같은 메모가 표시됩니다: 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 처음에는 그들이 미쳤다고 생각할지도 모릅니다. 아마도 이것이 오늘날 당신이 생각할 수 있는 많은 데이터 유출이 있는 이유일 것입니다. 하지만 이것은 모듈식 산술 모듈 12에 지나지 않습니다(비록 이상한 표기법이 있긴 하지만). 여러분은 그것을 모듈식 산술이라고 부르지 않았을 수도 있지만, 여러분은 시간을 알려주는 것을 배운 이후로 이런 종류의 계산을 해왔습니다. (이 방정식들을 다시 보고 시간을 더하는 것에 대해 생각해보세요.). 형식적으로 "시간 계산"은 합동성 이론에 의해 설명됩니다. 우리는 만약 a = b m..

Ron was Wrong, Whit is Right 문제 및 설명 여기 RSA 공개 키 묶음이 있습니다. 인터넷에 접속한 사람들로부터 그들이 보낸 메시지와 함께 수집되었습니다. excerpt.py 에서 볼 수 있듯이, 모든 사람이 PKCS#1 OAEP를 사용하여 자신의 메시지를 암호화했습니다. 암호 해독이 가능해서는 안 되지만, 일부 키에 문제가 있는 것은 아닐까요? 풀이 더보기 from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey import RSA msg = "???" with open('21.pem') as f: key = RSA.importKey(f.read()) cipher = PKCS1_OAEP.new(key) ciphertext = ciph..

Transparency 문제 및 설명 HTTPS를 통해 웹 사이트에 연결할 때, 서버가 보내는 첫 번째 TLS 메시지는 서버 TLS 인증서를 포함하는 ServerHello입니다. 브라우저는 TLS 인증서가 유효한지 확인하고 유효하지 않을 경우 TLS 핸드셰이크를 종료합니다. 검증에는 다음 사항이 포함됩니다: - 인증서의 이름이 도메인과 일치합니다 - 인증서가 만료되지 않았습니다 - 인증서는 최종적으로 브라우저 또는 운영 체제에서 신뢰하는 CA(인증 기관)의 루트 키에 의해 서명됩니다("신뢰 체인"을 통해) CA에는 인증서에 서명할 수 있는 권한이 있으므로 인터넷의 보안은 올바른 사용자에게 TLS 인증서를 발급하는 데 따라 달라집니다. 즉, 실제 도메인 소유자에게만 인증서를 발급해야 합니다. 그러나 Win..

Privacy-Enhanced Mail? 문제및 설명 인코딩 부분에서 살펴본 것처럼 암호화는 큰 정수, 원시 바이트, 16진수 문자열 등 매우 다양한 형식으로 데이터를 처리합니다. 암호화 데이터의 송수신을 지원하기 위해 몇 가지 구조화된 형식이 표준화되었습니다. 이러한 공통 데이터 형식을 인식하고 조작할 수 있습니다. PEM은 키, 인증서 및 기타 암호화 자료를 보내는 데 널리 사용되는 형식입니다. 모양은 다음과 같습니다 base64 인코딩된 데이터를 한 줄의 머리글과 바닥글로 감싸 데이터 구문 분석 방법을 나타냅니다. 헤더와 본문에 정확한 하이픈 수가 있어야 합니다. 그렇지 않으면 암호화 도구가 파일을 인식할 수 없습니다. base64 인코딩된 데이터는 DER 인코딩된 ASN.1 값입니다. 혼란스럽습니..

Marin`s Secret 문제 저는 제 비밀 목록에서 소수를 생성하는 초고속 방법을 찾았습니다. 풀이 더보기 #!/usr/bin/env python3 import random from Crypto.Util.number import bytes_to_long, inverse from secret import secrets, flag def get_prime(secret): prime = 1 for _ in range(secret): prime = prime

Infinite Descent 문제 큰 소수를 찾는 것은 느리기 때문에 최적화 방법을 고안했습니다. 풀이 더보기 #!/usr/bin/env python3 import random from Crypto.Util.number import bytes_to_long, isPrime FLAG = b"crypto{???????????????????}" def getPrimes(bitsize): r = random.getrandbits(bitsize) p, q = r, r while not isPrime(p): p += random.getrandbits(bitsize//4) while not isPrime(q): q += random.getrandbits(bitsize//8) return p, q m = bytes_..

Crossed Wires 문제 저는 친구들에게 비밀 플래그값을 보내기 전에 암호화해 달라고 부탁했지만, 그들은 제 키값을 사용하는 대신에 모두 자신들의 것을 사용했습니다! 도와주실 수 있겠어요? 풀이 더보기 from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse import math from gmpy2 import next_prime FLAG = b"crypto{????????????????????????????????????????????????}" p = getPrime(1024) q = getPrime(1024) N = p*q phi = (p-1)*(q-1) e = 0x10001 d = inverse(e, phi)..

Modulus Inutilis 문제 내 소수들은 지금 충분히 커야 합니다! 풀이 더보기 #!/usr/bin/env python3 from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes e = 3 d = -1 while d == -1: p = getPrime(1024) q = getPrime(1024) phi = (p - 1) * (q - 1) d = inverse(e, phi) n = p * q flag = b"XXXXXXXXXXXXXXXXXXXXXXX" pt = bytes_to_long(flag) ct = pow(pt, e, n) print(f"n = {n}") print(f"e = {e}") print(f"ct = ..

Manyprime 문제 1개의 주요 인자를 사용하는 것은 분명 좋지 않은 생각이었기 때문에 대신 30개 이상을 사용해 보겠습니다. 💡인수 분해에 시간이 오래 걸리는 경우 인수 분해 알고리즘을 읽어보고 이 시나리오에 최적화된 알고리즘을 사용하는지 확인합니다. 풀이 더보기 일단 n의 값들이 여러 소수가 있는것을 확인할 수 있다. 개인키 구하는 방법은 일단 n에서 나온 소수들을 p라고 하면 개인키는 (p1 -1)*(p2-1)*(p3-1).......(pn-1)이기에 이를 이용하여 평문값을 구하게 된다면 from Crypto.Util.number import long_to_bytes n = 58064239189884319292956385687089779965088315271876176293229248225215..

Monoprime 문제 왜 모든 사람들이 RSA를 위해 두 소수를 곱하는 데 집착합나요. 그냥 하나만 사용하는 게 어때요? 풀이 더보기 먼저 n의 값이 factordb통해 알아보았다. n의 상태는 P이고, n은 소수이다. 이때 오일러의 피함수를 보게 된다면 단일 소수, 즉 모노프라임 인 경우의 오일러의 피함수의 작동원리가 n-1이기 때문에 개인키의 값은 n-1이다. from Crypto.Util.number import long_to_bytes n = 17173137121806544412548253630224591541560331838028039238529183647229975274793460724647750850782728407576391026499532601025126849363050198981085..

Factoring 문제 지금까지 계수에 작은 소수의 제품을 사용해 왔지만, 작은 소수는 최신 방법을 사용하여 인수 분해할 수 있기 때문에 RSA에 그다지 좋지 않습니다. "작은 소수"란 무엇입니까? RSA 모듈리를 인수할 수 있는 팀에게 상금이 수여되는 RSA Factoring Challenge가 있었습니다. 이를 통해 대중은 다양한 키 크기가 얼마나 오랫동안 안전하게 유지될 수 있는지에 대한 통찰력을 얻을 수 있었습니다. 컴퓨터는 더 빨라지고 알고리즘은 더 좋아지기 때문에 암호학에서는 항상 주의를 기울이는 편이 신중합니다. 요즘에는 최소 1024비트 길이의 소수를 사용하는 것이 좋습니다. 이러한 1024비트 소수 두 개를 곱하면 2048비트의 계수가 됩니다. 2048비트 계수의 RSA를 RSA-2048..