일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Franklin-Reiter Related Message Attack
- overthewire
- rao
- 웹해킹
- shellcode
- bandit
- 드림핵
- Montgomery Reduction
- weak key
- spoofing
- RSA Common Modulas Attack
- arp
- 암호학
- Cube Root Attack
- XSS
- Crypto
- RSA
- CSRF
- return address overflow
- AES
- Bandit Level 1 → Level 2
- redirect
- dns
- 시스템해킹
- picoCTF
- OverTheWire Bandit Level 1 → Level 2
- dreamhack
- cryptography
- pycrpytodome
- Hastad
- Today
- Total
목록Algorithm (5)
암호(수학) 등.. 공부한 거 잊을거 같아서 만든 블로그
Montgomery Form 위 이미지에 있는 계산 방식은 Montgomery From 이라고 하는 계산방법이다. 몽고메리 폼에서의 a` = aR mod N와 b` = bR mod N을 곱하면 (aR mod N) * (bR mod N) = (abR)R mod N 이고, 이를 몽고메리 폼에 맞게 하기 위해 R^(-1)을 곱해준다. (abR)R*R^(-1) mod N =(abR) mod N 이러한 계산과정은 R^(-1)을 곱하고 N을 나눠야 하기 때문에 느리다. 따라서 아래의 알고리즘을 통하여 구하면 비트 쉬프트 연산을 통하여 구할 수 있다. Montgomery Reduction Algorithm 아래의 수식은 몽고메리 감산 알고리즘으로 T = (aR mod N) * (bR mod N)을 (abR) mod ..
이진 탐색 알고리즘이란? 이진 탐색 알고리즘이란 정렬된 배열을 탐색 범위를 절반으로 줄여나가면서 탐색하는 알고리즘이다. 예시 오름차순으로 정렬된 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 배열로 1을 찾는 예시를 들어보겠다. 먼저 배열의 중간 값을 배열의 길이와 2를 나눈 몫의 값에 위치한 값이라고 하자. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 의 중간 값인 5와 1을 비교하고, 1이 5보다 작으므로 탐색범위를 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 에서 [0, 1, 2, 3, 4] 으로 줄인다. 이제 [0, 1, 2, 3, 4]에서 중간 값인 2가 1보다 크므로 탐색 범위를 [0, 1] 로 줄인다. [0, 1] 에서 중간 값이 우리가 찾..
개요 일반적으로 매우 큰 지수승의 수에 대해서 연산하는 것은 많은 자원을 이용해야한다. 특히 모듈러 연산 x**e (mod n) 대해서 e가 크면 클수록 매우 많은 공간과 시간을 써야한다. 하지만 다행이도 모듈러 연산의 성질을 이용하여 연산의 오버헤드를 매우 크게 줄일 수 있다. 모듈러 연산의 성질 먼저 모듈러 연산에 대해 모르는 사람들이 있을 수 있기에 간단한 설명을 하자면, 단순하게 나머지를 구하는 연산이라고 말할 수 있다. 예를 들어 a와 b가 있다고 할 때, a를 b로 나눈 나머지를 구하는 것이 모듈러 연산을 수행한 것이다. 이 글은 모듈러 연산에 대한 설명을 위한 글이 아니므로 자세한 내용은 인터넷에서 찾자! 매우 찾기 쉽다 이 모듈러 연산에 대해서 여러가지 성질이 있지만 이 글에서 다룰 성질은..
버블 정렬 버블 정렬이란? 인접한 두 원소의 크기를 비교하여 대소관계에 따라 위치를 교환하거나 교환하지 않음으로 오름차순이나 내림차순으로 데이터를 정렬하는 알고리즘이다. 예시 위의 배열을 버블정렬을 통해 오름차순으로 한번 정렬해 보자 인접한 두 값을 비교하여 큰 값이 왼쪽에 있다면 (큰 값, 작은 값) 두 개의 값의 위치를 서로 바꿔주고, 반대되는 경우 (작은 값, 큰 값) 자리를 바꾸지 않는다. 이 과정을 수행하면 배열에서 가장 큰 값이 배열의 가장 오른쪽에 위치하게 된다. 배열에 가장 큰 값인 5를 오른쪽에 옮겼던 과정을 다시 수행한다. 이때 5는 이미 제자리를 찾았으므로 비교대상에서 제외한다. 비교를 수행하여 배열에서 두 번째로 큰 값인 4가 5 다음에 위치하게 된다. 4와 5가 제자리를 찾았으므로..
유클리드 알고리즘 유클리드 알고리즘이란? 유클리드 알고리즘이란 두 정수의 최대 공약수를 효율적으로 구하는 방법으로써 다음과 같은 정리를 이용한다, a = bp + r (0 0 else print(result[2] + result[1]) 모듈러 역원 구하기 확장 유클리드 알고리즘을 통하여 모듈러 연산의 역원을 구할 수 있다. 먼저 역원이라 함은 gcd(a, n) = 1인, a와 n이 있을 때, a * a(^-1)≡ 1 mod n 을 만족하는 a^(-1)을 모듈 n에 대한 a 의 역원이라 한다. a * a(^-1)≡ 1 mod n 은 n * p + a * a^(-1) = 1 꼴로 나타낼 수 있으며, 따라서 확장 유클리드 알고리즘을 이용하여 모듈 n에 대한 a의 역원인 a^(-1)을 구할수 있다. 예를 들어보..