암호(수학) 등.. 공부한 거 잊을거 같아서 만든 블로그

Franklin-Reiter Related Message Attack Franklin-Reiter Related Message Attack 은 두 개의 관련된 메세지에 대하여 동일한 RSA 키로 암호화 된 값을 알 때, 관련된 메세지의 값을 알 수 있는 공격이다. M이라는 메세지와 관련된 메세지인 M1, M2 메세지의 암호화 값인 C1, C2를 알고 있으면 M값을 구할 수 있다. 두 방정식 f1, f2는 X = M 일 경우 0을 값으로 가진다. ( f1(M) = f2(M) = 0 ) 즉, X-M 을 공통 인수로 가지게 되어 gcd 알고리즘을 통해 f1, f2의 공통 인수 X-M을 구할 수 있으며, 구해진 인수 X-M의 상수항 -M에 N을 더함으로 M을 구하게 된다. RSA의 공개키 e가 3일 경우 공통 ..

Hastad's Broadcast Attack 동일한 평문 M을 동일한 공개지수 e 를 사용하여 서로 다른 N값을 이용하여 암호화 한 값 C 알고 있을 때, 평문을 알아낼 수 있는 공격이다. (C, N 쌍이 e 크기 이상 만큼 필요하다.) 식의 크기를 줄이기 위해 공개 지수인 e의 값을 3이라 생각하고 하겠다. 아래의 C1, C2, C3, N1, N2, N3 를 알고 있다고 하자. 그러면 중국인의 나머지 정리 (CRT) 를 이용하여 M^3 mod N1 * N2 * N3 (M3 < N1 * N2 * N3) 의 값을 알아 낼 수 있다. 중국인의 나머지 정리를 이용하여 M^3를 구해보자. 위와 같이 M^3 mod N1 * N2 * N3 를 구할 수 있으며 M^3 < N1 * N2 * N3 이므로 이는 M^3 ..

RSA Cube Root Attack RSA의 공개 지수 e의 값이 3일때 시도할 수 있는 공격이다. C를 암호문, P를 평문이라 했을 때, 위 이미지와 같이 평문 P를 N과 C를 이용하여 세제곱근으로 식을 표현할 수 있다. 암호문 C와 N의 값을 알고 있고, e=3일 때, P^3 N인 경우, C + NK 에서 K에 정수를 대입하여 세제곱근이 정수가 나올때 까지 반복한다. 정수가 나오면 이는 평문 P의 값이다. P^3 > N 이므로 K의 값은 P^3을 N으로 나누었을 때의 몫이 0 이상의 정수이므로 0, 1, 2, .... 의 정수가 된다. 따라서 K의 값을 0부터 계속 1씩 증가하여 반복해 세제곱근..

RSA Common Modulus Attack 동일한 모듈러 값으로 각기 다른 공개지수 e1, e2 ( gcd(e1, e2) = 1 인 ) 를 사용하여 암호화 한 암호문의 평문을 알아내는 공격이다． 아래와 같이 평문 M이 있을 때, 각기 다른 공개지수 e1, e2로 암호화 한 값을 C1, C2라 하자. 확장 유클리드 알고리즘은 필요하다면 아래 페이지를 참고하자. 확장 유클리드 알고리즘 (Extended Euclidean Algorithm) 유클리드 알고리즘 유클리드 알고리즘이란? 유클리드 알고리즘이란 두 정수의 최대 공약수를 효율적으로 구하는 방법으로써 다음과 같은 정리를 이용한다, a = bp + r (0 0 else print(result[2] + result[1] heahgo.tistory.com ..

CRT(Chinese Remainder Theorem)를 이용하면 RSA복호화를 기존 복호화 방식보다 빠르게 할 수 있다. CRT를 이용한 빠른 RSA 복호화 증명 CRT에 의하여 (1), (2)를 만족하는 m이 유일하게 존재. 아래의 식을 위 식의 k에 대입 양변에 q 곱하면 m2 이항 p > q 라고 하면 위 식을 이용하여 복호화 하면 기존 복호화 방법인 보다 빠르게 복호화가 가능하다. (사전에 필요한 값 대부분을 미리 계산하기 때문) 하지만 m1, m2를 아직모르기에 m1 와 m2를 구해보자. m1, m2 구하기 이므로 이다. 따라서 이고 위수(order)가 페르마 소정리에 의하여 p - 1이므로 이다. m2도 위와 같은 방법으로 하면 다음과 같다. 이제 m1과 m2를 알았으므로 위 방법을 사용하여..