RSA

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

개념

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

생성 알고리즘

1. 512비트 이상의 큰 소수 p, q를 선택
pq
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(PP)가 전송받은 CipherText(CC)를 복호화 한 PlainText(P1P_1)과 같다는 걸 증명
  • P1=Cdmodn=(Pemodn)d=PedmodnP^1 = C^d  mod n = (P^e mod n)^d = P^{ed} mod n
  • ed=k×φ+1ed = k × φ⒩ + 1
  • P1=Pedmodn=Pk×φ+1modnP^1 = P^{ed} mod n= P^{k × φ⒩ + 1} mod n
  • P1=Pk×φ+1modn=PmodnP^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을이용해 PemodnP^e mod n을 계산
RSA_Encryption (P, e, n) {
	C = Fast_Exponentiation(P, e, n)
    retrun C
}
  • Decryption (복호화) : CipherText(C)와 비공개키 d, n을이용해 CdmodnC^d mod n을 계산
RSA_Decryption (C, d, n) {
	P = Fast_Exponentiation(C, d, n)
    retrun P
}

Fast_Exponentiation

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

y=a9=a10012=a8×1×1×ay= a^9 = a^{1001_2} = a^8 × 1 × 1 × a

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

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
}

0개의 댓글