대충공부한거적어두는블로그

보호되어 있는 글입니다.

이렇다고 한다.. 최대한 직관적으로 구현하고자 했다 (물론 더 간단한 방법도 있겠지만) 계수 (a,b,c,d) 간 관계식을 이용해서 코드를 짜면 될 것 같다 def extended_euclidean(X,Y): if X0: q = x//y r = x%y if r==0: break # GCD 구해짐 x,y,a,b,c,d = y,r,c,d,a-q*c,b-q*d return c,d,y x,y = map(int, input().split()) a,b,GCD = extended_euclidean(x, y) print(f'{a} * {x} + {b} * {y} = {GCD}') 물론 파이썬 라이브러리를 사용해서 개 ez하게 구할 수도 있다 from gmpy2 import gcdext gcd, s, t = gcdext..

RSA 암호화 알고리즘이란 - modular exponentiation operation 기반으로 한 암호화 알고리즘 - n과 e를 공개키로, d를 개인키로 사용하여 아래와 같이 exponentiation을 통해 암호화 및 복호화 한다 - key generaton 방식은 아래와 같다 // 먼저 적절한 소수 p와 q를 선택하여 n을 구한다 // e를 적절히 선택하고, 개인키 d를 역산한다 // 만약 attacker가 p, q, d 중 하나를 찾는다면 모든 ciphertext에 대해 decrypt가 가능할 것이다 취약점 분석 예제 1 from sympy import randprime, nextprime from secret import pt p = randprime(pow(2, 511), pow(2, 512..

RC4 알고리즘이란? - 암호화와 복호화에 동일한 shared key를 사용하는 symmetric encryption - 스트림 암호 중 하나로 전송 계층 보안(TLS, SSL) 등 여러 프로토콜에 사용되었던 암호 방식 - 256바이트 이내의 key와 256바이트 초기배열 S를 이용해 PlainText와 동일한 길이의 Key Stream을 생성하고, 각 바이트 XOR을 통해 key stream을 생성한다 - key stream을 안다면 xor을 통해 암호화 및 복호화가 가능하다 RC4 알고리즘 동작 방식 Step1. 초기 상태 벡터 S와 임의 벡터 T를 생성한다 - S와 T는 256바이트 벡터 - S[i]=i (i=0~255) 인덱스 값을 채우고, T에는 key를 반복적으로 채운다 Step2. KSA 알..

AES 암호화 알고리즘 - Advanced Encryption Standard, 블록 암호 - Block Size: 16 Bytes - Key size: 16 Bytes(AES128) / 24 Bytes(AES192) / 32 Bytes(AESE256) - plaintext 길이가 16*k보다 작을 때 padding을 붙인다 * 주로 PKCS#7 표준을 사용함 (padding 6개 필요하면 b'\x06'으로 채우고, 2개 필요하면 b'\x02'로 채우는) * plaintext 길이가 16의 배수이면 padding b'\x10'*16 을 뒤에 붙인다 - plaintext의 길이가 block size보다 클 때 어떻게? => mode of operation * ECB(Electronic CodeBook) m..

- 플래그(byte)를 long으로 바꾼 후 prime인지 확인 - q에 256bit 크기의 랜덤한 prime 넣음 - φ(n) = (p-1)(q-1) / e = 65537 / d = 228001~~~20490241918976205665073 인 RSA 암호화 같다 푸는 방향은 d * e ≡ 1 (mod φ(n)) ☞ d * e ≡ 1 (mod (p-1)(q-1)) ☞ d*e-1 ≡ 0 (mod (p-1)) ☞ d*e-1 = k (p-1) 형태 d와 e를 알기 때문에 d*e-1 의 약수들을 잘 살펴보면 p-1 구할 수 있겠다! - 무작정 브포 돌리면 케이스 너무 많기 때문에 https://www.alpertron.com.ar/ECM.HTM 이런 곳에서 먼저 num=d*e-1를 소인수분해해 약수 구한 다음..

23.06.24 Dreamhack CTF Season 3 Round #6 (🌱Div2) 문제이자 나의 첫 암호학 문제! Caesar 암호 평문의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 치환하는 단일 문자 치환 암호 - 알파벳 소문자만 +13 옾셋만큼 밀어서 치환하더라 RSA 암호 1. 배경지식 φ(n)는 오일러 파이 함수로, n 이하의 양의 정수 중 n과 서로소인 수의 개수 2. 키 생성 - 서로 다른 두 소수 p, q를 선택하여 n=p*q로 세팅한다 - 이 때 φ(n) = p*q - p - q + 1 = (p-1)(q-1) 이다 - φ(n)보다 작은 수 중 φ(n)와 서로소인 e를 선택한다 - d ≡ e^(-1) (mod φ(n)) 를 만족하는 적절한 d를 선택한다 => n, e 는 공개키..