RSA Blinding attack, Common modulus attack

• Extended_Euclidean

extended_gcd를 이용해서 역원을 구할 수 있다.

• Modular Exponentiation

밑, 지수, 나머지 계산할 값을 넣고, 지수를 2진수 형태로 바꾼 다음 바이너리 값에서 1에 해당하는 값들을 모두 곱한 후 다시 mod 계산을 해준다.

• Chinese remainder Theorem

확장 유클리디안 알고리즘을 이용해서 s와 t를 구하고 중국인 나머지 정리 이론 식으로 값을 구한다.

• Text-book RSA

우선 키 길이와 평문을 먼저 설정해준다.

rsa_genkey 함수에서 키 길이를 이용해서 랜덤한 서로소인 소수 p와 q를 생성한다. 소수를 생성할 때 is_prime함수로 소수를 생성하고, is_prime 함수 내부에서 밀러라빈 테스트 함수를 호출하여 소수를 검증한다.

p와 q를 이용해서 n을 만들고 오일러 함수(토션) 값을 추출한다.

토션과 서로소인 e 값을 뽑아낸다. e 와 토션 함수를 확장 유클리디안 알고리즘(inverse)을 이용해 역원을 구한다 ==> ed=1 mod 토션

pk는 n과 e이고, sk는 p, q, d가 들어가게 된다.

rsa_encrypt 함수로 평문을 암호화 시키고, rsa_decrypt 함수는 속도를 위해 복호화 할때 CRT를 호출해서 평문을 제작한다.

• RSA Common Modulus attack POC

e1과 e2를 extended euclidean algorithm을 이용해서 s와 t값을 구해서 각각의 암호화 된 평문을 mod_exp 연산을 해주고 그 값을 서로 곱한후 mod n을 해주면 평문이 나오게된다.

m = (c1^s * c2^t) mod n

도훈이가 고정된 e 값을 알고 있으면 이미 common modulus를 사용할 필요 없이 값을 알 수 있다고 해서 e 값을 두개로 조정해 줬다.

p=127, q=131, e1=11, e2=17

• RSA Blinding attack POC

Text-book RSA와 키 생성까진 같다. BlindSign 함수를 생성한다.

n과 서로소인 r을 생성하고, 이 r을 이용해서 위조된 평문을 제작한다.

위조된 평문으로 가짜 서명을 생성한후에 r의 역원을 곱해준다. 이 과정을 거치면 정상적인 서명이 완성된다.

이 서명으로 값이 제대로된 평문을 나오게 되면 진짜 서명처럼 사용할 수 있는 위조된 서명을 얻게 된다.