개념 설명 모듈러 연산 당신이 몸을 숙이고 암호학자의 노트를 본다고 상상해보라. 여백에 다음과 같은 참고 사항이 표기되어 있는 게 보인다. 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 처음엔 그들이 미쳤다고 생각할지도 모른다. 이것이 오늘날 많은 데이터유출의 이유라고 생각될 수도 있겠지만, 이것은 모듈러 12에 대한 모듈러 연산에 지나지 않는다. (비록 다소 엉성한 표기법일지라도 말이다.) 당신은 모듈러 연산을 사용해본 적이 없다고 할 수도 있겠지만, 당신은 시간을 말하는 법을 배운 이후로 이런 종류의 계산을 해오고 있다. (위 식을 다시 보고 시간을 더하는 것에 대해 생각해보라.) 형식적으로 "시간 계산"은 합동식 이론에 의해 설명된다. 우리는 두 정수가 $a \equiv b \bmod m$..
https://thfist-1071.tistory.com/entry/C-%EC%96%B8%EC%96%B4-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%A6%9D%EB%AA%85-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A1%9C-%EA%B5%AC [C 언어] 유클리드 호제법 증명과 재귀함수 구현 유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요. 유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다. 여담으로 최소공배수는 (두 수의 곱/gcd) thfist-1071.tistory.com 알고리즘, 자료구조 카테고리에 포함되어 ..
개념 설명 확장된 유클리드 알고리즘 a와 b를 양의 정수로 하자. 확장된 유클리드 알고리즘은 다음과 같은 정수 u, v를 찾는 효율적인 방법이다. a*u + b*v = gcd(a,b) ! 나중에 RSA를 해독하는 방법을 배울 때, Public exponent의 modular inverse를 계산하기 위해 이 알고리즘이 필요할 것이다. 두 소수 p = 26513, q = 33221을 사용하여 다음과 같은 정수 u, v를 구한다. p*u + q*v = gcd(p, q) u와 v중 낮은 숫자를 플래그로 입력한다. ! p와 q가 소수라는 것을 알고, gcd(p, q)가 무엇이라고 생각되는가? 확장된 유클리드 알고리즘에 대한 자세한 내용은 아래 페이지를 참조하자. http://www-math.ucdenver.ed..
Modular Arithmetic의 시작 개념 설명 (Greatest Common Divisor을 최대공약수라고 한다.) 최대공약수(GCD)는 두개의 양의 정수 (a, b)를 나누는 가장 큰 약수로 알려져있다. a=12, b=8의 경우 우리는 a: {1, 2, 3, 4, 6, 12}, b: {1, 2, 4, 8}로 약수를 계산할 수 있다. 이 둘을 비교하면 우리는 gcd(a, b) = 4라는 것을 알 수 있다. 이제 a=11, b=17을 예로 들어보자. a와 b는 모두 소수이다. 소수는 자기 자신과 1을 약수로 가지므로 gcd(a, b) = 1이다. 우리는 임의의 두 정수 a, b에 대해 gcd(a,b) = 1이면 a와 b는 서로소(coprime integers)라고 말한다. a와 b가 소수라면(a !=..
설명 https://cryptohack.org/courses/intro/xorkey1/ CryptoHack – Home A fun, free platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard? cryptohack.org 내 비밀키로 암호화 했는데, 당신은 절대 추측할 수 없을 것이다. ! 플래그 형식과 이 과제에 도움이 될 수 있는 방법을 기억하라. 예제 풀이 0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104 from ..
설명 https://cryptohack.org/courses/intro/xorkey0/ CryptoHack – Home A fun, free platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard? cryptohack.org 다음 몇 과제에서는 이전에 배운 내용을 사용하여 XOR 퍼즐을 더 풀어볼 것이다. 단일 바이트로 XOR을 사용하여 데이터를 숨겼지만 그 바이트는 비밀이다. 16진수부터 디코딩하는 것을 잊지 마십시오. 예제 풀이 73626960647f6b206821204f21254f7d694f7624662065622127..
개념 설명 https://cryptohack.org/courses/intro/xor1/ CryptoHack – Home A fun, free platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard? cryptohack.org 지난 과제에서는 XOR이 비트 수준에서 어떻게 동작하는지 보았다. 여기서는 XOR 작업의 속성을 다루고 플래그를 암호화한 일련의 작업을 무력화하는데 사용할 것이다. 이것이 어떻게 작동하는지에 대한 직관을 얻는 것은 나중에 특히 블록 암호 범주에서 실제 암호 시스템을 공격할 떄 크게 도움이 될 것이다. X..
개념 설명 https://cryptohack.org/courses/intro/xor0/ CryptoHack – Home A fun, free platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard? cryptohack.org XOR은 비트가 같으면 0을 반환하고 그렇지 않으면 1을 반혼하는 비트 연산자이다. 교과서에서 XOR 연산자는 ⊕로 표시되지만, 대부분의 과제와 프로그래밍 언어에서는 caret ^이 대신 사용된다. 더 긴 이진수의 경우 비트별 XOR: 0110 ^ 1010 = 1100이다. 우리는 먼저 정수를 십진법에서..
