[RSA] in Public-key cryptosystem

수식 입력이 번거로워서 수식 표현이 좀 매끄럽지 못합니다.

특히 주의해서 보실 것: 예를 들어 a의 역원인 경우, a역 이라 표현했습니다.

 

키 생성

public key: (e, n)이고, private key: d이다.

 

생성 단계

p, q 선택: p != q, p와 q는 소수
n 계산: n = p * q
psi(n) 계산: psi(n) = (p - 1)(q - 1)
e 선택: 1 < e < psi(n) - 1이며 psi(n)과 서로소
d 계산: d ≡ e역 mod psi(n)

암/복호화

암호화

c ≡ m^e mod n

 

복호화

m ≡ c^d mod n
 

효율적인 복호화

CRT를 활용한다. 즉, c^d mod n을, 아래와 같이 나누어서 하는 것이다.

    먼저, 
    m1 ≡ c^d mod p와
    m2 ≡ c^d mod q를 구한 뒤, 
    이들을 이용하여 아래를 계산한다:
    m ≡ [m1 * q * (q역 mod p) + m2 * p * (p역 mod q)] mod n

 

공격

선택 암호문 공격

공격자는 암호문 c'에 대한 평문 m'을 얻고자 함

공격자: y ≡ r^e * c' mod n에 대한 평문을 요청함 
피해자: y^d ≡ r^(ed) * c'^d ≡ r * c'^d ≡ r * m' (mod n)를 공격자에게 줌 
공격자: r역 곱해 m' (mod n) 얻음 

 

공통 법 공격

공격자는 암호문 c1, c2에 대한 동일한 평문 m을 얻고자 함

공격자: 동일한 m에 대해, n이 같은 두 수신자의 c1, c2, e1, e2, gcd(e1, e2) = 1을 앎
            re1 + se2 = 1을 만족하는 r, s 구함, r < 0이라 가정 
            c1^r * c2^s ≡ m^(e1*r) * m^(e2*s) ≡ m^(e1*r + e2*s) ≡ m (mod n)