본문 바로가기
Cryptography

RABIN, ElGamel 암호

by L3m0n S0ju 2023. 12. 8.

RABIN 암호

RSA 암호 시스템에서 공개키 𝑒=2로 고정한 경우

 


키생성
1. 𝑘∈ℤ, 4𝑘+3인 서로 다른 두 소수 𝑝와 𝑞를 선택
2. 𝑛=𝑝×𝑞
3. (𝑝,𝑞) 개인키,, 𝑛 공개키

 

 

암호화
𝑐 ≡ 𝑚^2  (mod 𝑛)

 

 

복호화

 

복호화 (𝑝와 𝑞가  4𝑘+3형태임을 이용)

 

𝑎1≡𝑐_1^((𝑝+1)/4)  (mod 𝑝), 𝑎2≡−𝑐_1^((𝑝+1)/4)  (mod 𝑝)
𝑏1≡𝑐_2^((𝑞+1)/4)  (mod 𝑞), 𝑏2≡−𝑐_2^((𝑞+1)/4)  (mod 𝑞)

 

 

CRT를 이용

𝑃1=CRT(𝑎1,𝑏1,𝑝,𝑞), 𝑃2=CRT(𝑎1,𝑏2,𝑝,𝑞), 𝑃3=CRT(𝑎2,𝑏1,𝑝,𝑞), 𝑃4=CRT(𝑎2,𝑏2,𝑝,𝑞)
{𝑃1,𝑃2,𝑃3,𝑃4} 중 하나가 평문

 

 

예시

키 생성
4𝑘+3의 형태인 𝑝=7과 𝑞=11
𝑛=𝑝×𝑞=7×11=77
𝑛=77, (𝑝,𝑞)=(7, 11).

 

 

암호화

m = 10 -> c ≡ 10^2 ≡ 100 ≡ 23 (mod 77) 

 


복호화
𝑐1 ≡ 23 ≡ 2 (mod 7), 𝑐2 ≡ 23 ≡ 1 (mod 11).
𝑎1≡2^((7+1)/4) ≡ 2^2 ≡ 4 (mod 7) ,𝑎2 ≡ −2^((7+1)/4) ≡ 2^2 ≡ −4 ≡ 3 (mod 7)
𝑏1≡1^((11+1)/4) ≡ 1^3 ≡ 1 (mod 11),   𝑏2 ≡ −1^((11+1)/4) ≡ 〖−1〗^3 ≡ −1 (mod 11)

 

 

CRT를 이용
𝑚1≡7×8×1+11×2×4≡56+88=144≡67 (mod 77)
𝑚2≡7×8×(−1)+11×2×4≡−56+88≡32 (mod 77)
𝑚3≡7×8×(−1)+11×2×(−4)≡−56−88≡−144≡−67≡10 (mod 77)
𝑚4≡7×8×1+11×2×(−4)≡56−88≡−32≡45 (mod 77)

 

 

4개의 값 중에 하나는 평문임을 알 수 있다.

-> 답이 4개가 나오기 때문에 복잡해서 실용성 떨어짐

 

 

 

 

 


Reduction을 통한 안전성 증명

 

 

 

Reduction이 뭐야면 A reducible to B 라고 한다면 A를 B를 통해 구할 수 있다는 의미이다. 즉 B가 A보다 어렵다고 할 수 있다.

 

위에 그림에서는 B reducible to A를 나타낸 것인데 B는 제곱근 문제, A는 인수분해 문제이다. n이 주어지면 B에서 x^2을 선택하여 A에 넘겨주고 A는 인수분해 문제를 계산할 수 있으므로 y가 출력된다. 만약  y가 기존 x가 아닌 다른 해를 구할 수 있으면 제곱근 문제를 해결할 수 있다.

 

참고로 제곱근 문제는 y = x^2에서 y를 통해 x를 구하는 문제이고 인수분해 문제는 y=a^k * b^r 처럼 y를 통해 인수들을 분해하는 문제이다. Rabin 암호는 제곱근 문제에 기반하고 있기 때문에 인수분해 문제를 해결할 수 있다면 Rabin 암호도 쉽게 풀 수 있다. 하지만 Rabin 암호를 해결한다고 해서 인수분해 문제를 풀 수 있는지는 아직 밝혀지지 않았다.

 

 

 

 

 

 


ElGamel 암호

 

이산대수문제(Discrete Logarithm Problem, DLP) 의 어려움에 기반

 

키생성
1. 큰 소수 𝑝를 선택
2. 1≤𝑑≤𝑝−2 의 범위에서 임의의 𝑑를 선택
3. ℤ_𝑝^∗에서 원시근(Primitive Root) 𝑒1을 선택
4. 𝑑와 𝑒1을 이용해 𝑒2 ≡ 𝑒1^𝑎  (mod 𝑝) 을 계산
5. 공개키는 (𝑒1, 𝑒2, 𝑝), 개인키는 𝑑

 

 

암호화
1. 임의의 값 𝑟 을 선택
2. 𝑐1≡𝑒1^𝑟  (mod 𝑝) 
3. 𝑐2≡(𝑚×𝑒2^𝑟 )  (mod 𝑝) 
4. 암호문 (𝑐1, 𝑐2)

 

 

복호화
𝑐2 × (𝑐1^𝑎 )^(−1)  mod 𝑝 
-> (𝑐2 × (𝑐1^𝑎 )^(−1) ≡ (𝑒2^𝑟×𝑚) × (𝑒1^𝑟𝑎 )^(−1) ≡ (𝑒1^𝑎𝑟)×𝑚×(𝑒1^𝑟𝑎 )^(−1) ≡ 𝑚  (mod 𝑝)

 

 

 

ElGamel 전자서명

키 생성
𝑦=𝑔^𝑥 (mod p), (𝑦,𝑔,𝑝)는 검증키, 𝑥를 서명키

 

서명 생성

1≤𝑘≤𝑝−2 의 범위에서 𝑝−1과 서로소인 정수 𝑘를 임의로 선택

𝛾≡𝑔^𝑘 (mod 𝑝)와 𝛿≡(𝑚−𝑥𝛾)𝑘^(−1) (mod 𝑝−1)를 계산
서명 값 𝑠=(𝛾,𝛿)

 

서명 검증
서명 값 𝑠=(𝛾,𝛿)와 서명한 메시지 𝑚, 검증키 (𝑦,𝑔,𝑝)
𝑦^𝛾 𝛾^𝛿 (mod 𝑝) 계산
-> 𝑦^𝛾 𝛾^𝛿≡𝑔^𝑥𝛾 𝑔^𝑘𝛿≡𝑔^(𝑥𝛾+𝑘𝛿)≡𝑔^(𝑥𝛾+𝑘(𝑚−𝑥𝛾) 𝑘^(−1) )≡𝑔^(𝑥𝛾+(𝑚−𝑥𝛾) )=𝑔^𝑚 (mod 𝑝)

 

따라서 서명한 값과 위 계산으로 구한 값을 비교해서 같으면 검증이 된다.

 

 

 

 

ElGamel 서명의 안전성

난수 𝑘가 같을 때 알려진 메시지 공격 모델에서 키 획득  

1. 두 개의 메시지 𝑚_1과 𝑚_2에 대하여 같은 𝑘를 사용한 서명 𝑠1과 𝑠2을 가지고 있다고 가정  
𝑠1 ≡ (𝛾1,𝛿1) ≡ (𝑔^𝑘  (mod 𝑝), (𝑚1−𝑥𝛾1 ) 𝑘^(−1)  (mod 𝑝−1)) 
𝑠2 ≡ (𝛾2,𝛿2) ≡ (𝑔^𝑘 (mod 𝑝), (𝑚2−𝑥𝛾2 ) 𝑘^(−1)  (mod 𝑝−1))

2. 𝛿1−𝛿2 = (𝑚1−𝑥𝛾1 ) 𝑘^(−1)−(𝑚2−𝑥𝛾2 ) 𝑘^(−1) = (𝑚_1−𝑥𝛾1−𝑚_2+𝑥𝛾2 ) 𝑘^(−1)

3. 𝛿1 − 𝛿2 값이 0이 아니라면 공격자는 𝑘^(−1)을 계산
𝑘^(−1) = (𝛿1−𝛿2) / (𝑚1−𝑚2)

4. 𝑥 = −(𝛿1𝑘−𝑚1) / 𝛾1 = −(𝛿2𝑘−𝑚2) / 𝛾2 (mod 𝑝−1)

 

x는 개인키 값인데 ElGamel 전자서명에서 개인키는 노출되면 안되므로 k가 같은 경우 안전하지 않다.

'Cryptography' 카테고리의 다른 글

암호학을 위한 기본 수학 지식  (0) 2023.12.02
[HackCTF] RSA3  (0) 2021.10.16
[AES 개념]  (0) 2021.10.12
[RSA 개념]  (0) 2021.10.12
[HackCTF] Classic Cipher -3  (0) 2021.10.09

댓글