[Cryptography] RSA

RSA

가장 널리 쓰는 공개 키 알고리즘 중 하나로 전자서명이 가능한 최초의 공개 키 알고리즘으로 알려져 있다.

개념

• Public Key : e, n
  ⤷ Plain Text의 크기는 n을 넘을 수 없으며 n은 1024 bits 이상의 수 이다
• Private Key : d
• $C = P^e mod n$
• $P = C^d mod n$

생성 알고리즘

1. 512비트 이상의 큰 소수 p, q를 선택
⤷ p ≠ q
2. n = p × q
⤷ n은 1024비트 이상의 수가 된다
3. φ⒩ = ( p - 1) × ( q - 1 )
4. φ⒩ 와 서로소인 e를 선택 ⇒ 1 < e < φ⒩

• Public Key : e, n
• Private Key : d = e⁻¹ mod φ⒩
  ⤷확장 유클리드 알고리즘 사용

RSA 정확성 증명과 예시

• 전송한 PlainText($P$)가 전송받은 CipherText($C$)를 복호화 한 PlainText($P_1$)과 같다는 걸 증명

• $P^1 = C^d  mod n = (P^e mod n)^d = P^{ed} mod n$
• $ed = k × φ⒩ + 1$
• $P^1 = P^{ed} mod n= P^{k × φ⒩ + 1} mod n$
• $P^1 = P^{k × φ⒩ + 1} mod n = P mod n$
  ⤷ 𖤐 φ⒩ 오일러의 정리 마지막 부분 참고!

Euclidean algorithm (유클리드 알고리즘)

두 수를 받아 나머지연산을 하여 최대 공약수를 구하는 알고리즘으로 golang을 이용하여 구현하면 다음과 같다

func main() {
	var a, b int
	reader := bufio.NewReader(os.Stdin)
	fmt.Fscanf(reader, "%d %d", &a, &b)  // a,b를 입력 받는다
	if a < b {
		a, b = b, a // 나머지 연산을 하기 위해 b가 a보다 클 경우 자리를 바꿔준다
	}
	gcd := 0  // 최대공약수 선언
	for {
		r := a % b 
		if r == 0 {
        	//나머지 연산 값이 0일 경우 최대 공약수 값은 0이 되며 반복문은 종료
			gcd = b
			break
		}
        // 나머지 연산 값이 0이 아닐 경우  a에는 b를, b에는 나머지 연산 값을 선언해서 반복 
		a = b
		b = r
	}
	fmt.Println(gcd)
}

𖤐 Extended Euclidean algorithm (확장 유클리드 알고리즘)

• RSA에서 Private Key를 구하기 위해 사용한다.

func main() {
	var a, b int
	reader := bufio.NewReader(os.Stdin)
	fmt.Fscanf(reader, "%d %d", &a, &b)
	r1 := a
	r2 := b
	t1 := 0
	t2 := 1
	for r2 > 0 {
		q := r1 / r2
		r := r1 - q*r2
		r1, r2 = r2, r
		t := t1 - q*t2
		t1, t2 = t2, t
		r = a % b
		if r1 != 1 {
        	// if r1 != 1일 경우 a, b가 최대공약수가 1이 아니므로, b의 inverse는 존재하지 않는다
			fmt.Println(0)
		}
		if t1 < 0 {
        	// 만약 t1이 음수가 되면 "t1 % n" 또는 t1을 더해주어서 해결한다
			t1 = a + t1
		}
	}
	fmt.Println(t1)
}

암호화와 복호화

• Encryption (암호화) : PlainText(P)와 공개키 e, n을이용해 $P^e mod n$을 계산

RSA_Encryption (P, e, n) {
	C = Fast_Exponentiation(P, e, n)
    retrun C
}

• Decryption (복호화) : CipherText(C)와 비공개키 d, n을이용해 $C^d mod n$을 계산

RSA_Decryption (C, d, n) {
	P = Fast_Exponentiation(C, d, n)
    retrun P
}

Fast_Exponentiation

$y= a^x mod n$을 계산하며 계산 시간을 단축하기 위해 Square and Multiply 개념을 이용해서 계산

$y= a^9 = a^{1001_2} = a^8 × 1 × 1 × a$

위와 같은 식을 golang의 rsa 패키지를 이용하여 구현할 수 있고, 패키지 안의 코드는 아래와 같다

func SquareAndMultiply(base int, exp int, modulo int) int {
	res := base
	// converst the number to a string of 0 and 1 in binary
	bin := strconv.FormatInt(int64(exp), 2)
	for e := 1; e < len(bin); e++ {
		res *= res
		res %= modulo
		if bin[e] == '1' {
			res *= base
			res %= modulo
		}
	}
	return res
}