012. 제곱(square) 2.6 제곱(square) 제곱은 같은 수끼리 곱하는 것으로 이미 구현된 곱셈을 사용할 수 있으나, 같은 수를 곱할 때 생기는 규칙성을 이용해서, 보다 효율적인 계산을 할 수 있다. 45261의 제곱을 구하는 것을 예로 들어보자. 답은 2048558121가 나와야 할 것이다. 일반적으로 연필로 계산하는 방식대.. 암호화프로그래밍/(Old)C-BIGINT 2013.07.31
011. 곱셈(multiply) 2.5 곱셈(multiply) 덧셈/증가 그리고 뺄셈/감소에 이어 곱셈에 대해 알아보자. 곱셈도 알고리즘이 그리 어렵지 않다. 덧셈 뺄셈과 마찬가지로 손으로 곱셈을 계산하는 방법을 그대로 구현하면 된다. 수행횟수는 덧셈/뺄셈이 O(n)정도를 보이는데 반해, 곱셈은 O(mn) 정도를 보인다. (m과 n은 곱.. 암호화프로그래밍/(Old)C-BIGINT 2013.07.30
010. 감소(decrese) 2.4 감소(decrese) 1만큼 감소시키는 함수이다. 1을 증가시키는 increse의 경우에도 add를 사용할 수도 있으나 효율성을 생각해서 별도 구현을 했듯이, decrese함수도 subtract함수로 구현할 수 있으나, 별도로 구현한다. 기본 원리는, 주어진 BIGINT값에 대해 가장 작은 자릿수를 -1해주고, 만약에 borrow.. 암호화프로그래밍/(Old)C-BIGINT 2013.07.30
009. 뺄셈(subtract) 2.3 뺄셈 앞 장에서 큰 수에 대한 첫 번째 연산으로 덧셈을 알아 봤다. 이번 장은 뺄셈이다. 뺄셈에 대한 알고리즘은 덧셈과 유사하다. 같은 자리끼리 더하는 것 대신에 빼주면 되고, 덧셈에서 올림이 발생한 반면, 뺄셈에서는 빌림(borrow)이 발생하는 것이 차이다. 뺄셈 알고리즘 이 알고리.. 암호화프로그래밍/(Old)C-BIGINT 2013.07.30
008. 테스트: 덧셈, 증가 테스트 테스트는 프로그래밍에 있어 너무나 중요한 부분이다. 특히 알고리즘이 관련된 복잡한 프로그래밍에 있어서는, 코드를 눈으로만 읽어서 그 결과값을 예측하는 것이 한계가 있기에, 여려 경우의 수를 고려하여 직접 실행결과를 확인해보는 것이 매우 중요하다. 따라서, 작성하는 .. 암호화프로그래밍/(Old)C-BIGINT 2013.07.30
007. 증가(increse) 2.2 증가(increse) 1만큼 증가 시키는 것을 구현해보자. 1 증가하는 것은, 앞에서 작성한 add함수를 써도 될 것이다. 즉, increse(A) = add(A,1,A) (마찬가지로 1 감소하는 것은 decrese함수를 나중에 구현할 텐데, 이것도 subtract함수를 써도 되긴 한다.) 그러나, 1증가/감소는 빈번하게 일어나는 연산이고 .. 암호화프로그래밍/(Old)C-BIGINT 2013.07.29
006. 덧셈(add) 2. 기본 연산 2.1 덧셈 큰 수에 대한 덧셈을 구현해 본다. 앞장에서 계속 얘기한 바와 같이 '큰 수'란 프로그래밍 언어에서 기본으로 제공하는 가장 큰 자료형으로 표현할 수 없는 큰 수이다. 그리고 이 '큰 수'는 기본 자료형의 배열로서 표현하기로 했다. 이 큰 수에 대한 덧셈이라는 것은, .. 암호화프로그래밍/(Old)C-BIGINT 2013.06.20
005. 큰 수에 대한 프로그래밍 1.1 프로그래밍 앞 장에서 큰 수에 대해서 왜 별도의 프로그래밍을 해야하는지 살펴봤다. 별도라는 것은, 프로그래밍 언어에서 지원하는 기본 자료형과 연산자를 사용하지 않고 새로운 표현방법과 연산함수들을 만들어야 함을 의미한다. (Java에서는 BigInter라는 클래스를 기본으로 제공해.. 암호화프로그래밍/(Old)C-BIGINT 2013.06.19
004. 큰 수 1. 큰 수(數)에 대한 프로그래밍 1.1 큰 수 컴퓨터에서의 수는 메모리에 저장되어 있는 일련의 비트 정보이며, 프로그래밍을 할 때는 해당 컴파일러에 약속된 데이터 타입에 따라 그 크기(몇 바이트 메모리가 할당될 것인지)와, 소수점이 있는 수인지, 그냥 정수형태인지 등이 결정된다. 예.. 암호화프로그래밍/(Old)C-BIGINT 2013.06.19
003. 목차 (not fixed yet) 목차 1. 큰 수에 대한 프로그래밍 1.1 큰 수 1.1 프로그래밍 2. 기본 연산 2.1 덧셈 2.2 뺄셈 2.3 증가/감소 2.3 곱셈 2.5 나눗셈 2.6 Modulus 2.7 최대공약수 3. 암호화 연산 3.1 난수 3.2 RSA 3.3 AES 3.4 Sha256 4. 암호화 응용 4.1 암호화, 복호화 4.2 서명, 검증 5. 응용 프로그래밍 5.1 BigNum Caculator 5.2 Open PGP 암호화프로그래밍/(Old)C-BIGINT 2013.06.19