지은이는 지은이

modular inverse 에 대한 설명은 다음 포스트 참고... 2024.01.16 - [study/수학&암호] - [CryptoHack] Extended GCD [CryptoHack] Extended GCD 베주 항등식 (Bezout's Identity) 두 정수의 최대공약수를 원래 두 수의 배수의 합으로 나타낼 수 있다. 이때 x 와 y 는 베주 계수(Bezout coefficient)라고 한다!! 정리하자면 GCD(a, b) = d라고 할 때, - ax + by = d lucykorea414.tistory.com 퀴즈) 3 mod 13의 inverse를 구하라~ 역수가 일단 존재하기 위해서는 3과 13이 서로소여야 한다!! (즉, gcd가 1 이어야 함) -> 3과 13은 서로소 O 그러면 오일..

페르마의 소정리 (Fermat's little theorem) 퀴즈) 273246787654가 65537와 서로소인지 먼저 확인해봅시다 결과는? 나머지가 있으므로 서로소임!!! 그러면 a와 p가 서로소일때 a^(p-1) mod p = 1 이므로 답은 1 ... ^^

퀴즈) x는 너무 쉽게 5인걸 알지만 y는 인간의 능력으로 풀 수 없기 때문에... 근데 a mod b = c이면 c mod b = a 이기 때문에 이를 이용해서 y = 8146798528947 mod 17 을 계산하면 됨!! 답은

베주 항등식 (Bezout's Identity) 두 정수의 최대공약수를 원래 두 수의 배수의 합으로 나타낼 수 있다. 이때 x 와 y 는 베주 계수(Bezout coefficient)라고 한다!! 정리하자면 GCD(a, b) = d라고 할 때, - ax + by = d를 만족하는 정수 x, y가 존재한다 - d는 정수 x, y에 대해서 ax + by로 표현할 수 있는 가장 작은 정수이다. - ax + by로 표현될 수 있는 모든 정수는 d의 배수이다. 확장 유클리드 호제법(Extended Euclidean algorithm) 위와 같은 베주 항등식과 비슷하게 확장 유클리드 호제법은 ax + by = d 라고 할때, d = GCD(a, b)에 대하여 (x, y)의 값을 찾는 효율적인 알고리즘이다!! 나중에..

GCD(Greatest Common Divisor): 최대공약수 -> 두 숫자 (a,b)의 가장 큰 약수 ex) a = 8, b = 12 인 경우 a의 약수 = {1, 2, 4, 8} b의 약수 = {1, 2, 3, 4, 6, 12} 따라서 gcd(a, b) = 4 if 만약, a 와 b 가 소수(prime number)인 경우 then gcd(a, b) 는 무조건 1 이다. => gcd(x, y) = 1 인 경우, x와 y는 서로소(coprime number) 이다. Euclidean algorithm (유클리드 호제법, 유클리드 알고리즘) 두개의 자연수의 최대공약수를 구하는 알고리즘 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수..

공부하면서... 내가 헷갈렸던 부분 정리! 1. 왜 xor 연산을 하려면 바이트형식으로 바꿔서 해야하는걸까? -> 주된 이유는 xor 연산이 비트 단위 연산이기 때문에!! 파이썬에서는 정수형끼리는 xor 연산 가능!! (자동적으로 2진수로 바꿔서 실행됨) ex) print(2^4) # 결과: 6 그러면 16진수는 어떨까? ex) hex_A = 0x1A hex_B = 0x3F byte_A = int.to_bytes(hex_A, length=1, byteorder='big') byte_B = int.to_bytes(hex_B, length=1, byteorder='big') result = bytes(x ^ y for x, y in zip(byte_A, byte_B)) result_hex = int.from..

Quiz) 풀이) 1. 문제에서 주어진 값을 바이트로 변환했다. 2. key 값을 모르는 상태인데, XOR의 특징 중 하나인 A^B = C 이면 C^A = B 인 것을 이용하여 플래그의 처음 부분인 crypto{ 를 cipher와 xor 하여 거꾸로 key를 찾는 방법을 사용했다. 3. 이때 결과로 myXORke+y~~ 라는 문자열이 나왔는데 myXORkey 라는 텍스트로 실험을 해봤다. 4. 똑같이 cipher와 myXORkey 를 xor 했더니 답이 바로 나왔다! 결과

Quiz) 풀이) 하나의 바이트로 xor 연산을 햇다고 하니 브루트포스를 써야겠군요... 요렇게 썼습니다 드림핵의 Single_byte_XOR 인가? 문제랑 유사하네요!! 그냥 하나의 바이트를 가지고 xor 연산을 하면 언젠간 플래그값이 나오므로 결과값은 다음과 같이 잘 나옵니다!

XOR의 4가지 특징 Commutative(교환법칙): A ⊕ B = B ⊕ A Associative(결합법칙): A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C Identity: A ⊕ 0 = A Self-Inverse: A ⊕ A = 0 교환법칙(Commutative): XOR 연산은 순서에 관계없이 같은 결과를 얻음 결합법칙(Associative): XOR 연산은 연속된 여러 항목을 괄호의 위치에 관계없이 결합할 수 있음 XOR 연산의 항등원은 0 자기 자신과 XOR 되면 0 퀴즈) 풀이) 헥스값을 먼저 바이트로 변환하고 계산해야함!! 처음에 이렇게 풀었더니 다음과 같은 오류가 발생함.. 보니까 바이트배열끼리의 XOR 연산은 지원되지 않는것 같음! 따라서 하나하나 다 정수형으로 변환해줘야하는 것 같다..

XOR 표현식 = ^ 2진수 예시) 0110 ^ 1010 = 1100 10진수를 XOR 하기 위해서는 2진수로 바꿔야한다. 문자를 XOR 하기 위해서는 각 문자를 유니코드로 바꾸고 다시 2진수로 바꿔서 계산해야함. quiz) Given the string label, XOR each character with the integer 13. Convert these integers back to a string and submit the flag as crypto{new_string}. 풀이) pwntools 라이브러리의 xor() 사용해서 쉽게 풀 수 잇음. 1. pwntools xor() 사용 하는 방법 2. 직접 xor 하는 경우