본문 바로가기
반응형

GF

 (104)
El Gamal El Gamal 암호화는 Diffie-Hellman 키 교환 방식을 기반으로 하는 공개키 암호화 방식이다. 수신자는 먼저 다음을 계산한다. 소수 p를 정한다. p보다 작은 x와 g를 정한다. y = (g^x) % p p, g, y를 공개한다. Encryption 전송할 메세지를 M이라 하고 다음을 계산한다. 이때 k는 p보다 작은 임의의 정수로, 공개하지 않는다. a = (g^k) % p b = ((y^k) * M) % p a와 b를 전송한다. Decryption by Third Party 제3자는 x 또는 k를 알아내면 복호화가 가능하다. x나 k를 알아내는 것은 이산 로그 방정식을 푸는 것과 같고, g와 p가 충분히 크면 풀이가 매우 오래 걸려 실효성이 없다(이것은 큰 소수를 알아내는 것이 중요한 이..
RSA RSA(Rivest, Shamir, Adleman)는 공개키 암호화 방식이며, 큰 숫자의 소인수 분해가 NP-문제로 풀기 어렵다는 것을 기반으로 한다(물론, 양자컴퓨터로는 금방 풀릴 것으로 보인다). 먼저, 수신측에서 다음을 계산한다. 서로 다른 두 소수 p, q의 곱인 n을 정한다. Euler's totient (n)을 구한다. 여기서는 (p - 1) * (q - 1)과 같다. 앞서 구한 Euler(n)의 값과 서로소이면서 더 작은 값 e를 정한다. (e * d) % Euler(n) = 1 을 만족하는 d를 구한다. 이후, n과 e를 공개한다. Encryption 메세지 M과 수신측이 제공하는 n, e를 바탕으로 C = (M^e) % n 를 계산한다. 암호문 C를 전송한다. Decryption by T..
Knapsack Cryptography Knapsack Cryptography는 배낭문제(Knapsack Problem)에서 비롯된 공개키 암호화 방법이다. Knapsack Problem에서 Superincreasing Sequence의 경우 다항 시간 내에 해를 구할 수 있지만, General Sequence인 경우 NP-문제가 된다. 수신자(private key를 갖는 쪽)는 다음을 미리 계산하고, H를 공개한다. S = [1, 3, 7, 13, 26, 65, 119, 267] n = 523 (bigger than sum of S) w = 467 (coprime with 523) wi = 28 (467 * 28 % 523 = 1) H = [467, 355, 131, 318, 113, 21, 135, 215] (S * w % n) 여기서 S..
5개의 수에서 중앙값 찾기 (Median Selection) 5개의 수에서 6번의 비교로 중앙값을 찾는 알고리즘을 알아보자. 이 방법은 Selection algorithm의 토대가 된다. 알고리즘 (C++) int median(int list[5]) { int w1, l1, w2, l2; if (list[0] > list[1]) { w1 = list[0]; l1 = list[1]; } else { w1 = list[1]; l1 = list[0]; } if (list[2] > list[3]) { w2 = list[2]; l2 = list[3]; } else { w2 = list[3]; l2 = list[2]; } if (w1 > w2) { if (list[4] > l1) w1 = list[4]; else { w1 = l1; l1 = list[4]; } } else ..
결정 트리 그리기(Decision Tree) 과제로 서로 다른 5개의 수를 가진 배열의 정렬을 위한 Decision Tree를 그려야 했다. 하지만 손으로 그리는게 너무 귀찮은 나머지 코드로 작성해버렸다. 작성언어는 Javascript(ES6)이며, 정렬이 잘 되는지 보기 위한 테스트 코드도 포함되어 있다. 아래 단색의 긴 코드가 너무 보기 힘들 수 있으므로, 사진 파일도 첨부했다. compare = (list, num) => { return (list[parseInt(num / 10) - 1] { if (compare(list, 12)) { if (compare(list, 34)) { if (compare(list, 25)) { // 1/2/5, 3/4 if (compar..
피보나치 수열의 증가 피보나치 수열은 다음과 같다. 번째 피보나치 수를 이라 하자. 이고, 이상의 에 대해 은 다음과 같이 정의된다. 위 식의 양 변을 로 나누면 다음의 식을 얻는다. 이고, 이 5 이상일 때 위 식을 재귀적으로 변형하면 다음의 결론을 얻는다. 그리고 이므로 즉, 이 5 이상일 때 이 성립한다. 그런데 이것은 일 때도 성립함을 확인할 수 있다. 따라서 는 모든 자연수 에 대하여 성립한다. 즉, 피보나치 수열은 이상으로 빨리 증가함을 알 수 있다. 추가 라 하자. (이때 ) 즉, 피보나치 수열에서 인접한 두 항의 비율은 에 수렴하는데, 이 값은 황금비(Golden Ratio)다.
Firebase와 함께 PWA 만들기 이전에 Lighthouse에 대해 쓴 글이 있다. Lighthouse를 통해 우리의 웹이 얼마나 '좋은가' 평가해볼 수 있다. 내가 현재 개발/유지 중인 UOSTime은 성능에서 매우 좋지 않은 점수를 받았고, 약간의 개선을 해놓은 상태이다. 그런데 PWA에 관심이 생겨 Lighthouse도 알게 되었지만, 정작 이미 만들어진 웹을 PWA로 바꾸는건 생각보다 힘든 일이었다. 그래서 깔끔하게, 처음부터 PWA를 만들어보기로 했다. 그리고 아직 한 번도 안 써본 Firebase도 써보기로 했다. 공부해야 할 것이 왕창 늘었다!! 시작 node.js가 설치되어 있어야 한다. 무작정 Firebase에 가서, 프로젝트 추가를 눌렀다. 프로젝트 이름은 일단 'test'로 했다. 아직 아무것도 모르기 때문이다. 그러..
하노이 타워 알고리즘의 시간복잡도 하노이 타워에서 원판 이동의 최소 횟수 및 그 순서를 찾아내는 코드는 아래와 같이 간단히 작성된다. (C언어로 작성됨) void move(int from, int to) { printf("move from %d to %d\n", from, to); } void hanoi(int n, int from, int by, int to) { if (n == 1) move(from, to); else { hanoi(n - 1, from, to, by); move(from, to); hanoi(n - 1, by, from, to); } } 위 코드에 따르면, hanoi함수의 시간복잡도 f(n)은 다음과 같이 재귀적으로 풀이된다. (여기서 f(1) = 1 이라 하자) f(n) = 2f(n - 1) + 1 = 4f(n ..

티스토리툴바