[암호학](-)[RSA 구현 3]

정수론 수업을 듣고 흥미로운 문제를 들었다.
n차 합동방정식은 n개의 서로 다른 해를 가지는데 왜 RSA는 복호화가 잘 되는가?
이거에 대해 알아본 결과.
A를 특정 값으로 제한해서 복호화가 망가지는 걸 억제하는 것이였다.

 

A값의 제한으로 여러 해 나오지 않게 하기

m = pq (p, q는 소수)
gcd(ϕ(m), k) = 1 에서 암호화는 c ≡ a^k (mod m) 이다.
당연히 c는 양수(암호문은 항상 양수만 생각)이고 m에 대해 유일하다.
 
그럼 문제의 복호화는?
x ≡ c^u ≡ a (mod m) 이다.
이때 gcd(ϕ(m), k) = 1 이므로 선형방정식의 정리에 의해
ku-ϕ(m)v = 1에서 해 ui, vi를 구할 수 있고 식을 변형하면 ku ≡ 1 mod(ϕ(m))이다.
gcd(ϕ(m), k) = 1이므로 선형합동방정식의 정리에 의해
만족하는 u는 mod(ϕ(m))에서 1개밖에 안나온다. (유일성!!!)
 
c^u ≡ a^ku ≡ a*a^ϕ(m)v (mod m)
만약 gcd(a, m) = 1이라면 오일러 정리에 의해
    a*a^ϕ(m)v ≡ a*(1^v)≡ a (mod m)
    따라서 gcd(a, m) = 1이라면 항상 c가 a로만 복구될 수 있다. (유일성!!!)
그러나 gcd(a, m) != 1이라면?
    아쉽게도 그럴 일 자체를 방지한다.
    m = 두 큰 소수의 곱 = pq
    gcd(a, m) != 1이려면 a|m이거나 m|a여야 한다.
        a|m인 경우: a = p or q or pq
        m|a인 경우: a = kpq
    여야 하는데 메세지 a를 p와 q보다 작게 설정하면 문제가 해결된다.
이를 위한 방법 중 하나로 블록으로 쪼개기를 사용할 수 있다.

 

블록으로 쪼개기

블록 암호 방식: 평문(a)를 일정 자릿수마다 쪼개서 블록으로 만들고 각 블록을 암호화 하는 방식
만약 블록 크기로 평문이 나누어 떨어지지 않는다면 패딩을 넣어 맞춘다.
[암호학 둘러보기 3], [암호학 둘러보기 6]의 알고리즘 들이 있다.
(물론 블록으로 쪼갠다는 거지 RSA가 블록 암호라는 소리는 전혀 아니다!)

• 예)
  예를 들어 a = 123456789 이고 p, q가 적어도 5자리 이상의 소수라고 하자.
  그리고 블록 크기를 5보다 작은 4라고 한다면
  a1 = 1234, a2 = 5678, a3 = 9000 의 3개의 블록으로 쪼갤 수 있다.
  ai < p, q이고 p, q는 1과 자신으로만 나누어 떨어지므로 gcd(ai, p or q) = 1이다.
  따라서 복호화 과정에서 문제는 없다.그리고 이것을 각각 복구하면 된다.
  
  실제로 p = 10007, q = 10009, k = 10037로 a 블록들을 암호화 한다면
  c1 = 57433639
  c2 = 84925178
  c3 = 86777414
  로 암호화할 수 있다.

 

또 다른 문제?

이건 정수론 말고 컴퓨터 구현에서 문제가 발생하는데,
특정한 자릿수의 암호문인 나오는 일반적인 블록 암호 알고리즘과 달리
RSA 암호화는 mod연산을 사용하므로 자릿수가 천차만별로 달라질 수 있다.
그러나 블록 단위로 쪼갰으면 블록 단위로 복호화 해야 할텐데 블록을 구별할 수가 없다!
예) c1 = 8 c2 = 3213213 이면 보낸 데이터는 83213213일텐데 이걸 어떻게 구별하는가?
해결책은 여러가지가 있다.

• 구분자
  말 그대로 데이터 중간에 블록을 표시할 수 있는 기호를 넣어주는 것이다.
  예) 8, 3213213
• 블록 길이 정보 저장
  데이터를 전송할 때 블록의 길이 정보도 같이 받고 그에 맞게 블록을 해석하면 된다.
  예) 83213213, 블록 길이 정보 = (1, 7) -> 8 3213213
• 패딩
  블록이 가질 수 있는 최대 크기 (0~m-1)에 맞춰 블록 크기를 정하고 블록의 남는 공간 앞에 0을 삽입한다. 그리고 데이터 전송 시 블록 크기를 전송한다.
  예)
      m = 100160063 일 때 최대 9자리의 블록 크기를 가질 수 있다.
      따라서 000000008003213213, 블록크기 = 9 로 전송하면
      000000008, 003213213로 구분하고 앞에 있는 0을 지워
      8, 3213213으로 해석한다.