W.Diffie 와 M.E.Hellman, 암호화의 새로운 방향, IEEE 정보론 저널, IT-22. 6 일, 1 1 월 1976, 644-654 면
단방향 활판 문 함수는 다음 조건을 충족하는 함수 f 입니다.
(1) 주어진 x 는 y = f (x) 를 쉽게 계산할 수 있습니다.
(2) 주어진 y 는 x 가 y=f(x) 가 되도록 계산하기 어렵다.
(계산의 난이도 x=f- 1(Y) 는 계산이 상당히 복잡하고 실제적인 의미가 없다는 것을 의미합니다. ) 을 참조하십시오
(3) δ가 존재할 때 x 를 쉽게 계산하여 y=f(x) 가 주어진 y 에 대해 해당 x 가 존재할 경우 y = f (x) 를 쉽게 계산할 수 있습니다.
참고: 1*. (1) 및 (2) 만 단방향 함수라고 합니다. 제 (3) 조는 함문 특성이라고 하고, δ는 함문 정보라고 한다.
2*. 트랩 함수 F 가 암호화 함수로 사용될 때 공개될 수 있습니다. 이는 암호화 키를 공개하는 것과 같습니다. 이 시점에서 암호화 키는 공개 키라고 하며 Pk 로 기록됩니다. F 함수의 디자이너는 δ를 비밀로 하고 이를 암호 해독 키로 사용합니다. 이때 δ는 키라고 하며 Sk 로 기록됩니다. 암호화 함수가 공개되기 때문에 누구나 정보 X 를 y=f(x) 로 암호화한 다음 함수 설계자에게 보낼 수 있습니다 (물론 안전하지 않은 채널을 통해 전송할 수도 있음). 설계자가 Sk 를 소유하고 있으므로 x=f- 1(y) 를 해석할 수 있습니다.
3*. 단방향 트랩 함수의 특성 (2) 은 도청자가 가로채는 암호문 y=f(x) 에서 X 를 추론하는 것이 불가능하다는 것을 나타냅니다.
Diffie 와 Hellman 은 이정표가 있는 문장 중 암호학의 사상을 제시했지만 공개 키 암호학의 실제 예도 제시하지 않았고, 실제 활판문이 있는 단방향 함수도 찾지 못했다. (윌리엄 셰익스피어, Northern Exposure (미국 TV 드라마), 스포츠명언) 그러나 단방향 함수의 예를 들어 Diffie-Hellman 키 교환 알고리즘을 제시했습니다. 이 알고리즘은 유한 필드에서 이산 로그를 계산하는 데 어려움이 있습니다. f 를 유한 도메인으로 설정하고 g ∝ f 는 f * = f \ {0} =
Diffie-Hellman 키 교환 프로토콜 설명: Alice 와 Bob 은 큰 소수 P 와 큰 정수 G, 1
Alice 와 Bob 이 개인적으로 대화하기를 원할 때, 그들은 다음과 같이 진행할 수 있다.
(1)Alice 는 큰 난수 x 를 보내고 계산합니다.
X=gx (모듈 p)
(2) 밥이 큰 난수 x 를 선택합니까? 를 클릭하고 x 를 계산합니까? = GX? (국방부)
(3) 앨리스는 밥에게 x 를 보냈다. 을 눌러 섹션을 인쇄할 수도 있습니다 밥이 엑스테? 앨리스에게 보내주세요
(4) 앨리스 계산 K=(X? ) x (모드 p); 밥 k? =(X) X? (mod P), 쉽게 알 수 있습니다, K=K? =g xx? (국방부).
(4) 에 따르면 Alice 와 Bob 은 동일한 비밀 값 K 를 받았고, 양측은 K 를 암호화 암호 해독 키로 사용하여 기존의 대칭 키 알고리즘을 사용하여 안전하게 통신합니다.
참고: Diffie-Hellman 키 교환 알고리즘은 미국과 캐나다에서 특허를 가지고 있습니다.
3 RSA 공개 키 알고리즘
RSA 공개 키 알고리즘은 1978 에 Rivest, Shamir 및 Adleman 이 제안했습니다 (ACM 통신 참조). 제 265438 권 +0. 제 2 호. 2 월 1978, 120- 126 면).
Z/(n) 은 Zn 으로 표시됩니다. 여기서 n = pqp 와 q 는 소수이며 다릅니다. 만약
Z*n? {g ∝ Zn | (g, n)= 1}, Z*n 이? G 와의 (n) 차수 곱셈 그룹? (n)? 1(mod n) 및? (n)=(p- 1)(q- 1).
RSA 암호 시스템은 다음과 같이 설명됩니다.
첫째, 일반 텍스트 공간 p = 암호문 공간 C=Zn. P 175 를 참조하십시오.
A. 키 생성
선택 p, q, p, q 는 서로 다른 소수이고, 계산 n=p*q,? (n)=(p- 1)(q- 1), 정수 e 를 선택하여 (? (n), e)= 1,1< E<? (n)), d 를 계산하여 d=e- 1(mod? (n)), 공개 키 Pk={e, n }；; 개인 키 Sk={d, p, q}.
0 일 때
MK? (n)+ 1? M(mod n), 그리고 ed? 1 (mod? (n)), 가시 (Me)d M(mod n)
B. 암호화 (e, n) 일반 텍스트: m.
C. 암호 해독 (d, p, q 사용)
암호문: c 일반 텍스트: M=Cd(mod n)
참고: 1* 은 암호화 및 암호 해독에서 한 쌍의 역연산입니다.
2*, 0 < M< 의 경우 n, (m, n) ≠ 1 이면 m 은 p 또는 q 의 정수 배수입니다. M=cp, 시작 (CP, q) =/ (q)? 1(mod q) M? (q)? (p)? 1(q 항)
M 있어요? (q) =1+kq; M=cp 양 방향 곱셈은 동일합니다.
M 있어요? (q)+ 1 = m+kcpq = m+kcn
M 있어요? (q)+ 1? M (현대)
예: Bob 이 p= 10 1, Q = 1 13 을 선택하면 n =/kloc-; (n) =100 ×112 =11200; 그러나 1 1200 = 26× 52× 7, 양의 정수 E 는 암호화된 인덱스로 사용할 수 있으며 E 가 2,5,7 로 나눌 수 없는 경우에만 사용할 수 있습니다 (실제로 Bob 는 φ(n) 을 분해하지 않습니다)
D=e-1? 6597(mod 1 1200) 따라서 Bob 의 암호 해독 키 d=6597 입니다.
Bob 은 한 디렉토리에 n= 1 14 13 및 e=3533 을 게시합니다. 이제 Alice 가 Bob 에게 일반 텍스트 9726 을 보내려고 한다고 가정해 봅시다.
97263533 (mod11413) = 5761
한 채널에 암호문 576 1 을 보냅니다. 밥이 암호문 576 1 을 받았을 때 그의 비밀 암호 해독 인덱스 (개인 키) d = 6597: 57616597 (MOD1/KLL
주: RSA 의 보안은 암호화 함수인 ek(x)=xe(mod n) 가 단방향 함수이기 때문에 사람들이 역전하는 것은 불가능하다. 밥이 해독할 수 있는 함정은 n=pq 를 분해하는 거야, 알았지? (n)=(p- 1)(q- 1). 따라서 암호 해독 개인 키 d 는 유클리드 알고리즘에 의해 해결됩니다.
4 RSA 암호 시스템 구현
구현 단계는 다음과 같습니다. Bob 은 구현자입니다.
(1) 밥이 두 개의 큰 소수 P 와 Q 를 찾았습니다.
(2) 밥 계산 n=pq 및? (n)=(p- 1)(q- 1).
(3) 밥은 난수 e (0) 를 선택합니다
(4) 밥 계산 d=e- 1(mod? (n))
(5)Bob 는 카탈로그에 N 과 E 를 공개 키로 공개했다.
비밀번호 분석가가 RSA 시스템을 공격하는 열쇠는 n. Ruofen 을 분해하는 방법입니다
해결이 성공하면 n=pq 가 된다. φ (n) = (P- 1) (Q- 1) 을 계산해 대중으로부터 계산할 수 있다
오픈 E, 암호 해독 D. (추측: RSA 해독, 분해 N 은 다항식입니다.
상당하다. 그러나 이 추측은 지금까지 믿을 만한 증거를 제시하지 못했다! ! ! ) 을 참조하십시오
따라서 RSA 를 안전하게 하려면 P 와 Q 가 충분히 큰 소수여야 합니다.
분석가는 다항식 시간 내에 n 을 분해할 수 없습니다. 제안된 선택
P 와 q 는 약 100 의 십진수입니다. 모듈 n 의 길이 요구 사항은 최소한 입니다
5 12 비트입니다. EDI 공격 표준에서 사용하는 RSA 알고리즘은 n 의 길이를 다음과 같이 지정합니다
5 12 에서 1024 비트까지 128 의 배수여야 합니다. 국제 숫자
서명 표준 ISO/IEC 9796 은 N 의 길이가 5 12 비트라고 규정하고 있습니다.
기존 정수 분해 알고리즘에 저항하기 위해 RSA 모듈 N 의 소인자를 분석했다.
P 와 q 에도 다음과 같은 요구 사항이 있습니다.
(1)|p-q| 크다. 보통 p 와 q 의 길이는 같다.
(2)p- 1 과 Q- 1 에는 각각 매크로 요소 p 1 과 q 1 이 포함되어 있습니다.
(3)P 1- 1 및 q 1- 1 매크로 요소 p2 와 Q2 를 각각 포함합니다.
(4)p+ 1 및 q+ 1 에는 각각 매크로 요소 P3 과 Q3 이 포함되어 있습니다.
암호화 속도를 높이기 위해 e 는 일반적으로 EDI 국제 표준의 e = 2 16+ 1, ISO/IEC9796, 심지어 e = 3 과 같은 특정 작은 정수로 사용됩니다. 이 시점에서 암호화 속도는 일반적으로 암호 해독보다 10 배 빠릅니다. 다음으로 암호화 해독 산수 연산을 연구합니다. 주로 모듈 N 의 제곱연산입니다. 유명한' 제곱합 곱셈' 방법은 xc(mod n) 를 계산하는 모듈러 곱셈 횟수를 최대 2l 로 줄입니다. 여기서 L 은 이진이 지수 C 를 나타내는 자릿수입니다. N 을 k 비트, 즉 k=[log2n]+ 1 을 이진으로 표현하도록 설정합니다. L≤ k 는 xc(mod n) 가 o(k3) 시간 내에 완성될 수 있도록 합니다. (o(k2) 시간 내에 곱셈을 완료할 수 있다는 것을 쉽게 알 수 있습니다. ) 을 참조하십시오
제곱합 곱셈 알고리즘
지수 c 는 바이너리 형태로 표시됩니다.
C=
Xc = xc0 × (x2) c1×… × (x2t-1) CT-1
미리 계산: x2=xx
X4=x22=x2x2
。
。
。
X2t- 1 =x2t-2*x2t-2
Xc 계산: ci= 1 에 해당하는 모든 x2i 를 곱하여 xc 를 얻습니다. 까지/매우
T- 1 곱셈이 더 많습니다. 참고서 177 쪽을 참고하여 계산을 해 주세요.
Xc(mod n) 알고리즘 프로그램:
A = xc c = c0+c 1 2+..+CT-12t-1= [CT-/kloc]
5 RSA 서명 체계
서명의 기본 개념
전통적인 서명 (필기 서명) 기능:
(1) 서명은 서명된 문서의 물리적 부분입니다.
(2) 실물 부분을 검증하고 대조해 확인 목적을 달성한다. (위조하기 쉽다)
(3) 충실한' 복제' 는 쉽지 않다! ! !
정의: (디지털 서명 체계) 서명 체계는 서명 알고리즘과 검증입니다.
증명 알고리즘은 두 부분으로 구성됩니다. 5 행 관계 그룹 (P, A, K, S, V) 을 통해 조각할 수 있습니다.
(1)P 는 가능한 모든 메시지의 제한된 세트입니다.
(2)A 는 가능한 모든 서명의 제한된 세트입니다.
(3)k 는 제한된 키 공간으로 가능한 키의 제한된 집합입니다.
(4) k ∩ k 의 경우 서명 알고리즘 sigk ∩ s 와 해당 검증 알고리즘 verk ∩ v 가 있습니다.
서명: p a 및 Verk:P×A {true, false} 조건 충족: 임의의 x ∝ p, y ∝ a. 서명 체계가 있는 서명: ver (x, y) = {
참고: 1*. 모든 k ∩k, 함수 Sigk 및 Verk 는 다항식 시간 함수입니다.
2*.Verk 는 공용 함수이고 Sigk 는 비밀 함수입니다.
3*. 나쁜 사람 (예: Oscar) 이 X 에 Bob 의 서명을 위조하려고 한다면 계산상 불가능하다. 즉, 주어진 X 는 Bob 만 서명 Y 를 계산하여 verk (x, y) = true 로 만들 수 있습니다.
4*. 서명 체계는 무조건 안전할 수 없다. 충분한 시간만 있으면 오스카는 항상 밥의 서명을 위조할 수 있다.
RSA 서명: n=pq, P=A=Zn, 정의 키 세트 K={(n, e, p, q, d)}|n=pq, d*e? 1(mod? (n)}}
참고: n 과 e 는 공개 키입니다. P, q, d q 및 d 는 비밀 (개인 키) 입니다. X ∩ p 의 경우, 밥은 x, k ∩ k.sigk (x)? Xd(mod n)? Y (모듈 n)
그래서
Verk(x, y)= 참 x? 잎 (현대)
(참고: e, n 은 열려 있습니다. 서명 (x, y) 이 옳고 그른지 공개적으로 확인할 수 있습니다! ! 밥의 서명인지 여부)
참고: 1*. 누구나 서명 Y 에 대해 x=ek(y) 를 계산하여 임의 메시지 X 에 Bob 의 서명을 위조할 수 있습니다.
2*. 서명 메시지의 암호화된 전송: Alice 가 Bob 의 서명 메시지를 암호화한다고 가정해 봅시다. 일반 텍스트 X 의 경우 Alice 는 X 의 서명, y=SigAlice(x) 를 계산하고 Bob 의 공개 암호화 함수인 eBob 를 사용하여 계산합니다.
Z=eBob(x, y), Alice 는 z 를 Bob 에 보내고, Bob 은 z 를 받은 후 첫 번째 단계는 암호 해독이다.
DBob(Z)=dBobeBob(x, y)=(x, y)
그런 다음 확인하십시오.
VeraAlice (x, y) = true
Q: Alice 가 서명하기 전에 메시지 x 를 암호화하면 결과는 다음과 같습니다
어때요? Y=SigAlice(eBob(x))
Alice 는 (Z, Y) 를 Bob 에게 보내고, Bob 은 먼저 Z 를 해독하여 X 를 얻습니다. 그런 다음
VerAlice 는 x 에 대한 암호화된 서명 y 를 확인합니다. 이 방법의 잠재적 문제
문제는 오스카가 이 쌍 (z, y) 을 얻으면 그의 서명을 사용할 수 있다는 것이다
앨리스의 서명 바꾸기
Y? =SigOscar(eBob(x))
(참고: 오스카는 명문 X 를 모르더라도 암호문 eBob(x) 에 서명할 수 있다. 오스카 스텔스 전태 (Z, Y? 밥, 밥, 그는 일반 텍스트 x 가 오스카에서 왔다고 추측할 수 있다. 그래서 사람들은 먼저 서명하고 암호화할 것을 제안한다. ) 을 참조하십시오
6.EIGamal 프로그램
EIGamal 공개 키 암호 시스템은 이산대수 문제를 기반으로 합니다. P 를 양보하다
최소한 150 십진수 소수, p- 1 은 큰 소수 계수가 있습니다. Zp 는 제한된 도메인입니다.
α가 Zp 의 원본이면 ZP * =
고유한 정수 a, (필수, 0≤a≤ P-2) 를 계산하는 방법
αa=β (모드 p)
A 를 a = log α β로 씁니다.
일반적으로 a 를 해결하는 것은 계산에 어려움이 있다.
Zp* 의 Egamal 공개 키 시스템에 대한 설명: 일반 텍스트 공간을 P=Zp* 로 설정하고 암호문은 비어 있습니다.
C=Zp*×Zp*, 키 공간 정의 K={(p, α, a, β )|β=αa(mod p)}
공개 키는 p, α, β입니다.
키 (개인 키): a
앨리스는 비밀 난수 k ∩zp-/Alice-0/,암호화 일반 텍스트 x 를 취합니다.
Ek(x, k)=(y 1, y2)
여기서 y 1 = α k (mod p), y2 = x β k (mod p) 입니다.
밥이 암호를 해독했습니다.
Dk(y 1, y2) = y2 (y1α)-1(mod p)
참고: 1*. Y2 (y1α)-1= x (α a) k (α ka)-1= x! !
2*. EIGamal 암호화 알고리즘을 사용하여 다음과 같은 기반 서명 체계를 제공할 수 있습니다.
Alice 는 명문 X 에 서명하려고 하는데, 먼저 그녀는 비밀 난수 K 를 서명으로 삼았다.
서명
시그 (x, k)= (? ,? ) 을 참조하십시오
그 중? =αk(mod p),? =(x-a? ) k- 1 (모델 p- 1)
그렇죠, x? ∝ ZP * 및 ∩ ZP-1,정의 Verk(x,? ) = 참 같음
베타? 알파? =αx (모듈 p)
서명이 올바르게 구성된 경우 유효성 검사는 다음을 수행한다는 점에 유의해야 합니다
성공입니다. 왜냐하면
베타? 알파? = 알파 a? αk? (mod p) = 알파 a? +k? (국방부)
위에서 아세요? =(x- a? ) k- 1(mod p- 1) 을 도입할 수 있습니다.
K? =x- a? (mod p- 1) a 가 있습니까? +kx (모드 p)
그래서 베타? = αx (모듈 p)
이 서명 방안은 NIST (National Standards and Technology Institute) 에서 서명 표준 (1985) 으로 확인되었습니다.
RSA 의 경우 다음 웹 사이트를 방문하십시오.
Www.RSAsecurity.com