라떼는말이야

※ 본 게시글은 모듈러 연산에 대해서 알고 있다는 전제하에 진행한다. 페르마의 작은 정리 (Fermat's little theorem) 페르마의 작은 정리에서 암호기술에 많이 응용되는 분야는 유한체에서의 역원 계산이다. 즉, 정수 a의 역원을 계산하는 방법으로 활용된다. 위 정의를 살짝 변형하면 다음과 같이 표현할 수 있다. 위 식을 잘 보면 a의 곱셈에 대한 역원을 생각해 볼 수 있다. 그 식은 다음과 같다. a의 역원은 a ^ (p-2) mod p이다. 이처럼 나타낼 수 있는 상황은 p가 소수일 경우에만 가능하다. 예제 1 위의 예제에서 3의 201 제곱에서 201은 10 x 20 +1로 표현할 수 있다. (3^10)^20 x 3에서 3^10은 mod11을 취했을 때 페르마의 작은 정리에 의해서 1이..

유클리드 알고리즘 (Euclidean algorithm) 두 정수 사이의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다. 유클리드 알고리즘의 동작 두 정수 a, b가 있을 때 r은 a ÷ b의 나머지로 정의한다. 즉, r = a % b이다. (a > b로 가정) 위 프로세스와 같이 나머지가 0이 될 때까지 두 번째 인자 값을 첫 번째 인자 값에 넣고, 나머지를 두 번째 인자 값에 넣는다. 예시 Q1. 2740과 1760의 최대공약수 계산 2740과 1760의 최대 공약수는 20이다. Q2. 25와 60의 최대공약수 계산 25와 60의 최대공약수는 5이다. 위 예제에서는 r1과 r2 중 어느 쪽이 커도 상관 없다는 것을 보여준다. 구현 gcd = lambda a, b..

0. RSA의 키 생성 알고리즘 RSA의 키 생성 알고리즘은 다음과 같다. 자세한 건 이전 글을 참고 바란다. 2020/06/18 - [알고리즘/RSA] - [RSA] 소개 & 키 생성 알고리즘 서로 다른 큰 소수 p, q를 선택한다. (p ≠ q) N = p x q를 계산한다. φ(N) = (p - 1) x (q - 1)을 계산한다. φ(N) 보다 작고, φ(n)와 서로소인 자연수 e를 선택한다. (gcd(e, φ(N))=1, 1 < e < φ(N)인 e 선택) d x e를 φ(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. ( de ≡ 1 mod φ(N) ) , 유클리드 호제법 이용 KU = {e, N}, KR = {d, N}이 된다. 위 알고리즘에서 해결해야 할 문제들이 있다. 1. 큰 소수 ..

RSA는 공개키 암호 알고리즘 중 하나이다. 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)이 공동 개발하였으며, 이들의 이름 앞글자를 따서 RSA가 되었다. RSA의 안정성은 큰 수에 대한 소인수 분해의 어려움을 기반으로 한다. 일반적으로 공개키 암호는 공개키와 개인키가 한 쌍을 이루며, 공개키로 암호화한 메시지를 개인키로 해독하여 열어볼 수 있기 때문에 암호화 키와 복호화 키가 다르다는 점에서 비대칭키 알고리즘의 특징을 가진다. RSA에서 사용되는 용어들 표기 설명 p, q 매우 큰 두 소수 (p≠q) N p x q gcd(a, b) a, b의 최대 공약수 φ(N) (p - 1) x (q - 1) a mod n a ÷..