이 블로그의 저작물은 별도
표시가 없는 한 아래 조건에
따라 사용 가능합니다
- 저작자 명시 필수
EC Elgamal 을 사용한 암호 설명 ECDH 에서 서로간에 난수 A, B 를 교환하여 대칭키를 만들고 형성된 대칭키로 AES 같은 암복호를 할수 있다. 그러나 대칭키를 사용하지 않고도 EC Elgamal 방식으로 암복호를 할수 있다. 설명 Alice 와 Bob 간 암호 통신에서 1. Plain Text 는 35 이다. 밑은 5, 모듈로는 89 이다. 2. Alice 의 개인키는 13 이다. 3. Bob 의 개인키는 8 이다. 4. X^a,b 의 89 모듈로는 다음과 같다. - Alice : 5^13 mod 89 => 40 - Bob : 5^8 mod 89 => 4 위 계산된 두 숫자 40 과 4 를 교환한다. 이때 공격자 Eve 는 40 혹은 4 로부터 개인키 13 혹은 8 을 추출할 수 없다. 5. Alice 와 Bob 은 상대편의 지수부분 ( 비밀키 ) 를 몰라도 전송된 각각의 40, 4 를 가지고 암호 키를 계산할 수 있다. 즉 - Alice : 4^13 mod 89 = 16 - Bob : 40^8 mod 89 = 16 암호 키값은 16 이다. 6. 평문 ( Plain Text ) 35 를 암호화 해서 보내고자 한다. - CT ( Cipher Text ) : - CT <= 16*35 mod 89 => 26 : X^ab * P mod N - 35*16 mod 89 => 26 7. 형성된 암호키값 16 의 모듈로 역수는 39 이다. [G,C,~]=gcd(16,89); % C => 39 matlab 에서 위 함수를 사용하면 모듈로 인버스를 구할 수 있다. ------- 모듈로 역수를 구하는 것은 어렵다. 16*39 mod 89 = 1 인데 이 값은 0 에서 88 까지 대입해 봐야 한다. 운이 나쁘면 89 번을 대입해야 하는데 각각을 대입하여 모듈로 결과값이 1 이 나오면 그 값이 16 의 역수이다. 이건 좀 이상한데 그렇다고 하자. 사실 나도 잘 모르겠다. ( 계산을 운에 맞겨야 한다. ) 모듈로의 역수를 구하는 방법은 0 부터 계속 한개씩 증가시켜서 모듈로 결과가 1 이 나올때 증가시켜서 대입한 그 값이 역수이다. 여기서는 대입해본 결과 39 를 얻었다. 39 번의 모듈로를 계산 했다는 이야기다. 8. 복호 ( 암호의 반대 ) 를 하려면 암호된 값 26 에 16 의 모듈로 역수 39 를 곱하면 나온다. - CT = X^ab * P mod N => 26 - PT = CT * X^ab(-1) mod N 26*39 mod 89 = 35 - 복호된 값이 암호된 값 35 와 동일하다. matlab 확인 결과 mod(5^13,89) % ans = 40, Prv K : 13 N = 89 mod(5^8,89) % ans = 4, Prv K : 8 mod(4^13,89) % ans = 16 Encryptin Key mod(40^8,89) % ans = 16 Encryptin Key
mod(16*35,89) % ans = 26 CT : Cipher Text [G,C,~]=gcd(16,89); % C => 39
mod(16*39,89) % ans = 1 Inverse 16 mod(26*39,89) % ans = 35 : Decrypted V = Plain Text ================================ A = 151; M = 541; [G, C, ~] = gcd(A,M); if G==1 % The inverse of a(mod b) exists only if gcd(a,b)=1 ModMultInv = mod(C,M) else disp('Modular multiplicative inverse does not exist for these values') end ModMultInv = 43 Ex2. mod(5^11,89) % ans = 55, mod(5^7,89) % ans = 72, mod(55^7,89) % ans = 34 Encryptin Key mod(72^11,89) % ans = 34 Encryptin Key 참고 mod(mod(72^5,89)*mod(72^6,89),89) = 34, 큰수 72^11 = 72^5*72^6 mod(34*57,89) % ans = 69 CT : Cipher Text
[G,C,~] = gcd (34,89) ; % C==> -34 ==> 55 mod(34*55,89) % ans = 1 Inverse mod(55*69,89) % ans = 57 : Decrypted V = Plain Text
나머지 연산의 곱셈 역원
나머지 연산의 곱셈 역원
나머지 연산의 곱셈 역원 2016년 1월 2일 baekjoon 댓글 (7개) 확장 유클리드 알고리즘 , 나머지 연산 , 역원 정수 $a$ 를 $m$ 으로 나눈 나머지 연산의 곱셈 역원은 $a \times a^{-1} \equiv 1 \pmod m$ 을 만족하는 $a^{-1}$ 을 말합니다. 즉, $a^{-1} \equiv x \pmod m$ 을 만족하는 $x$ 를 말합니다. 역원은 $a$ 와 $m$ 이 서로소인 경우에만 존재합니다. 역원을 구하는 코드를 작성해보면 아래와 같습니다. for (int i=1; i<m; i++) { www.acmicpc.net
4. 모듈러 인버스 모듈러 역수(역원)에 대해 알아보고자 한다. 우선 13/14 mod 11은 몇일까? 우선 13 * 14^-1 mod 11로 생각해보자. 그렇다면 모듈러 특성에 의해 ((13 mod 11) * (14 mod 11)^-1) mod 11이 되고 2 * 3^-1 mod 11이 된다. 이때 3^-1을 N으로 두자. 그러면 2 * N mod 11이 되고 N을 구하기 위해서는 3 * x mod 11 = 1이 되는 x를 찾으면 된다. x는 결국 4, 15, 26, 37 ...이 됨을 알 수 있다. 따라서 13/14 mod 11 = 2 * N mod 11 = 2 * 4 mod 11 = 8이 된다. 이제 이를 좀더 자세하게 보자. (5 / 3) mod 11은 뭘까? 우리는 곱의 형태인 (5 * 3^-1) mod 11로 나타낼 수 있다. 우리는 어떤 숫자에 역수를 곱하면 그 결과값은 1이 나와야한다. 예를들면 2 의 역수인 2^-1 즉, 1/2 둘을 곱하면 2*(1/2) = 1이다. 3 * x mod 11은 1이 나와야하므로 x = 4라는 역수를 구할 수 있다. 물론 x = 1/3도 되지만 분수 값이 아닌 정수 값으로 구하고 mod 11이라는 모듈러가 있기에 4도 가능해진다는 것이다. 따라서 우리는 5 / 3 mod 11이 5 * 3^-1 mod 11과 같으며 5 * 4 mod 11과 같고 결국 9라는 답을 도출 할 수 있다. 출처: https://www.crocus.co.kr/1231 [Crocus] Diffie-Hellman 방식의 문제점은 키 사이즈가 너무 크다는 것이다. 이것을 ECC 커브를 사용한 암호 알고리듬을 적용하면 지수 계산을 가산계산으로 변경할 수 있다. 예를 들면 a^n = A 에서 n 값이 암호가 되려면 n 의 경우의 수가 충분히 커야 하는데 이 지수값을 계산하는데 2380 bit 가 소요된다. 이런 것을 그대로 사용한 것이 RSA 알고리듬이다. RSA 는 큰 두개의 소수가 소인수분해되기 어렵다는 것을 기초로 하여 암호를 교환한다. 문제는 이런 연산이 2048bit, 4096 bit 정도의 지수 연산을 필요로 하기 때문에 시간과 메모리를 많이 필요로 한다. ECC 는 이런 지수 부분의 연산을 가산으로 바꾸었다. 또 소수만 사용해서 계산하는 것을 일반 난수를 사용해서 계산할 수 있게 했다. 물론 모듈로는 소수지만 이것은 공개되는 수 이므로 미리 정해진 수를 사용해도 된다. RSA 의 문제점은 큰 소수를 발생시키는 알고리듬이 꽤 어렵기도 하다. 4096 비트 소수를 찾아내고 이것이 소수인지 알려면 머리가 꽤 아프다. ECC 는 이런 큰 수를 2230 bit => 228bit 로 줄였다. 물론 암호화 경우의 수는 같다. ================================== RSA 소인수 분해 DSA 설명 Ex, prime 100 이하의 소수 p, q 선정 example p = 89, q=97 n = p*q = 8633 Pi_n = ( p-1) * ( q-1 ) = 8448 1< e < 8448 중에서 임의의 수 선정 Select e 1 < e < Pi_n e = 8363 ===== matlab 프로그램 % primes(100) = 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 p = 89; q = 97; n = p*q ; Pi_n = (p-1)*(q-1);
% n = 8633 ; % sel. e : % 1 < e < Pi_n % Pi_n = 8448
e = 6323 ;
for D = 1 : Pi_n if ( mod(e*D,Pi_n) == 1) d=D; end end
% n, e : pub Key % d : prv Key % after calc get % d = 6011 n, e : 공개키 : n = 8633, e = 8363 d : 비밀키 : d = 6011 타원곡선암호, Elliptic Curve Cryptography[출처] 타원곡선암호, Elliptic Curve Cryptography (3)|작성자 ilovemylif 어떤 암호방식 체계를 사용하는지에 대해 알아보았으니 예제를 살펴보도록 하겠다. GF(13) 상에서, y2 = x3 + 2x + 7 곡선을 사용한다고 가정하고, generator (1, 10)을 사용한다고 가정하자. G = (1,10) 2G = G + G 이는 앞의 식에 대입하면(직접 직선을 만들어서 구할 수도 있다) 타원곡선암호, Elliptic Curve Cryptography (1) 식 R = (x3, y3) x3 = s2 - x1 - x2 y3 = s(x1 - x3) - y1 s = (y2 - y1) / (x2 - x1) when P != Q = (3x12 + a) / 2y1 when P = Q s = (3 + 2) / (20) mod 13 = 5 x 7-1 mod 13 = 5 x 2 mod 13 = 10 x3 = 102 - 2 = 9 - 2 = 7 mod 13 y3 = 10(1 - 7) - 10 = 8 mod 13 2G = (7, 8) 3G = G + 2G = (1, 10) + (7, 8) s = (8 - 10) / (7 - 1) = -2 x 6-1 = -2 x -2 = 4 mod 13 x3 = 16 - 1 - 7 = 8 mod 13 y3 = 4(1- 8) - 10 = 1 mod 13 3G = (8, 1) 4G = 2G + 2G = (3, 0) 5G = 2G + 3G = (8, 12) = -3G 6G = 3G + 3G = (7, 5) = -2G 7G = 6G + G = (1, 3) = -G 8G = ∞ 이런 식으로 타원곡선 암호 체계를 구성할 수 있고, 이 때의 개인키를 3, 공개키를 (1, 10), 3(1, 10) = (8, 1)이라고 두고 송신자의 난수는 2, 평문 (6, 3)을 암호화하는 과정과 복호화 하는 과정은 암호화 C1 = 2(1, 10) = 2G = (7, 8) C2 = 2(8, 1) + (6, 3) = 2 x 3G + (6, 3) = (7, 5) + (6, 3) = (4, 1) 복호화 M = C2 - 3C1 = (4, 1) - 3(7, 8) = (4, 1) - 3 x 2G = (4, 1) + 2G = (4, 1) + (7, 8) = (6, 3) 이렇게 예쁘게 할 수 있다.[출처] 타원곡선암호, Elliptic Curve Cryptography (3)|작성자 ilovemylif %{ GF=13, Y2=X^3+2X+7, G(1,10) X3=S^2-X1-X2 Y3=s*(X1-X3)-Y1 S=(Y2-Y1)/(X2-X1) if P~=Q S=(3*X1^2+a)/2Y1 if P=Q prv_Key=3, pub_Key : G(1,10), 3*G(1,10) ( prv_Key* (1,10)) %} %======================================= clear; a= 2; b = 7; Mod = 13; N = 8; NxG = 1:( N*2) ; NxG = reshape (NxG,N,2); NxG = NxG - NxG ; nxg = 1:N; nxg = nxg'; NxG=[nxg, NxG]; for n = 1:N if ( n == 1) NxG(n,2) = 1 ; NxG(n,3) = 10; % 초기 1G 값(1,10) elseif ( n == N ) % Final Value NxG(n,2) = 8888; NxG(n,3) = 8888 ; % inf.
elseif ( mod (n,2)==0 ) % xG + xG same size %======================================= X1 = NxG(n/2,2); Y1 = NxG(n/2,3); % X1 = NxG(n-1,1); % Y1 = NxG(n-1,2); % S=3*X1^2/2*Y1 if P=Q
Sx=3*X1^2+a; Sy = 2*Y1; SX=mod(Sx,Mod); SY = mod(Sy,Mod); [G,C,~] = gcd ( SY,Mod); if ( C < 0 ) C = C+ Mod ; endif S=mod( SX*C, Mod ) ; %X3=S^2-X1-X2 %Y3=s*(X1-X3)-Y1 X3=S^2-2*X1; X3=mod(X3,Mod); Y3=S*(X1-X3)-Y1; Y3=mod(Y3,Mod); NxG( n,2) = X3; NxG( n,3) = Y3;
elseif ( mod(n,2)==1 ) % xG + (x+1)G odd size % ex. 3G = G+2G %================================ % 5G = 2G+3G (7,8) + (8,1) % S=(Y2-Y1)/(X2-X1) if P~=Q % S=3*X1^2/2*Y1 if P ~= Q % Sx=3*X1^2+2; Sy = 2*Y1; X1 = NxG((n-1)/2,2); Y1 = NxG((n-1)/2,3);
X2 = NxG((n-1)/2+1,2); Y2 = NxG((n-1)/2+1,3); DY = mod((Y2-Y1),Mod); DX = mod((X2-X1),Mod); [G,C,~] = gcd ( DX,Mod); S=mod(DY*C,Mod); %X3=S^2-X1-X2 %Y3=s*(X1-X3)-Y1 X3=S^2-X1-X2; X3=mod(X3,Mod); Y3=S*(X1-X3)-Y1; Y3=mod(Y3,Mod); NxG( n,2) = X3; NxG( n,3) = Y3;
endif end NxG %{ 1 1 10 2 7 8 3 8 1 4 3 0 5 8 12 6 7 5 7 1 3 8 8888 8888 %} % 8G = 4G+4G = (3,0)+(3,0) : S= 0 G1=[1,10] G2=[7,8] G3=[8,1] G4=[3,0] G5=[8,12] G6=[7,5] G7=[1,3] % G8 : inf. prv_Key=3 % pub_Key : G(1,10), 3*G(1,10) ( prv_Key* (1,10)) pub_Key = G3 % Reeciver_Rand = 2 PT (6,3) % CT PT? % CT1= 2G; (7,8) % CT2 = 2*3G+PT = (7,5)+(6,3) = (4,1) %================================ X1 = 7; Y1 = 5; X2 = 6; Y2 = 3; DY = mod((Y2-Y1),Mod); DX = mod((X2-X1),Mod); [G,C,~] = gcd ( DX,Mod); S=mod(DY*C,Mod); %X3=S^2-X1-X2 %Y3=s*(X1-X3)-Y1 X3=S^2-X1-X2; X3=mod(X3,Mod); Y3=S*(X1-X3)-Y1; Y3=mod(Y3,Mod); [X3,Y3] % X3, Y3 => (4, 1) % CT = (4,1) % M = CT2-CT1 = (4,1)-2G = (4,1)-2x3G = (4,1)-6G = (4,1)+2G= (4,1)+(7,8) %================================ % S=(Y2-Y1)/(X2-X1) if P~=Q % S=3*X1^2/2*Y1 if P ~= Q % Sx=3*X1^2+2; Sy = 2*Y1; X1=4;Y1=1; X2=7;Y2=8; DY = mod((Y2-Y1),13); DX = mod((X2-X1),13); [G,C,~] = gcd ( DX,13); S=mod(DY*C,13) %X3=S^2-X1-X2 %Y3=s*(X1-X3)-Y1 X3=S^2-X1-X2; X3=mod(X3,13) Y3=S*(X1-X3)-Y1; Y3=mod(Y3,13) % X3, Y3 => (4, 1) % CT = (4,1) %{ M = CT2-CT1 = (4,1)-3x2G= (4,1)-6G = (4,1)+2G becase 8G = inf. 8G = -6G +8G = 2G M = (4,1) + (7,8) = (6,3) %} X1 = 4; Y1 = 1;
X2 = 7; Y2 = 8; DY = mod((Y2-Y1),Mod); DX = mod((X2-X1),Mod); [G,C,~] = gcd ( DX,Mod); S=mod(DY*C,Mod); %X3=S^2-X1-X2 %Y3=s*(X1-X3)-Y1 X3=S^2-X1-X2; X3=mod(X3,Mod); Y3=S*(X1-X3)-Y1; Y3=mod(Y3,Mod); [X3,Y3] |
작성하신 에 이용자들의 신고가 많은 표현이 포함되어 있습니다.
다른 표현을 사용해주시기 바랍니다.
건전한 인터넷 문화 조성을 위해 회원님의 적극적인 협조를 부탁드립니다.
더 궁금하신 사항은 고객센터로 문의하시면 자세히 알려드리겠습니다.