F 상의 타원곡선(elliptic curve)이란 y2 + a1*x*y + a2*y = x3 + a3*x2 + a4*x + a5, 단, a1,a2,a3,a4,a5 ∈ F 형태의 방정식으로 주어진 곡선을 말한다.
(I) 체 F의 표수(characteristic)가 2와 3이 아닌 경우
체의 표수(characteristic) p 가 2와 3이 아닐 때는, 위 타원곡선을 적당히 이동을 하면 y2 = x3 + a*x + b 형태로 나온다. 이 때 암호론에서 사용하는 곡선은 변형된 타원곡선이 smooth인 경우, 즉 우변의 방정식이 중근(4*a3+27*b2 ≡0(mod p) 이면 중근존재)을 갖지 않을 경우에, 변형된 타원곡선 상의 점과 무한 원점(0)(항등원)으로 구성된 점들 사이에 적당한 덧셈연산을 정의하면 가환군이 된다는 것을 이용한 암호방법이다. 곡선상의 점 P=(x1, y1), Q=(x2, y2)의 덧셈연산은 아래 그림과 같이 두 점 P,Q를 지나는 직선과 타원곡선과 만나는 제3의 교점(x,y)을 x축에 관해 대칭한 점(x, -y)을 P+Q=(x3, y3) 로 정의한다. 계산을 해보면 아래(1)(2)와 같다. 제3의 교점이 없으면, 즉 직선이 y축과 평행하면 (3)과 같이 정의한다.
단, P + Q = (x1, y1) + (x2, y2) = (x3, y3)
(1) (x1 ≠x2)인 경우 (지나는 직선이 y축에 평행하지 않음)
x3 = (y2-y1 / x2-x1)2 - x1-x2 ; y3 = (y2-y1 / x2-x1)(x1-x3) - y1.
(2) (x1 = x2 이고 y1 = y2 ≠0)인 경우 (지나는 직선이 접선)
x3 = (3x12+a / 2y1)2 - x1-x2 ; y3 = (3x12+a / 2y1)(x1-x3) - y1.
(3) (x1 = x2 이고 y1 = -y2)인 경우 (지나는 직선이 y축에 평행)
P + Q = 0(무한원점). 즉, Q = -(x1, y1) = (x1, -y1).
P + 0(무한원점) = P.
(II) 체 F의 표수(characteristic)가 2 경우
이 경우의 체의 원소수는 2p (단 p 는 양의 정수)인 유한체가 되므로, 타원곡선은 다음 중 어느 하나와 동형이 된다.
♡ y2 + y = x3.
♡ y2 + xy = x3 + x.
♡ y2 + y = x3 + x + 1.
여기서는 간단히 계산하기 위해 y2 + y = x3 을 사용하여 덧셈연산을 한 것을 나열한다.
(1) (x1 ≠x2)인 경우 (지나는 직선이 y축에 평행하지 않음)
x3 = (y2+y1 / x2+x1)2 + x1+x2 ; y3 = (y2+y1 / x2+x1)(x1+x3) + y1 + 1.
(2) (x1 = x2 이고 y1 = y2)인 경우
x3 = x14 ; y3 = y14 + 1.
(III) 체 F의 표수(characteristic)가 3인 경우
500 이하의 다음 소수를 이용하여 연습해보기 바란다. 아래 연습에서 수의 입력 방법에 따라 이상한 결과가 나오면 왜 그런지 이유를 생각해 볼 것.
5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
♡ 타원곡선(Elliptic curve)상의 점 찾기
타원곡선 y2 = x3 + ax + b (mod p)의 연습입니다. p>3이고 4a3 + 27b2 ≡0(mod p)(중근)이 아닌 a,b 쌍을 대입하세요.
97 소수(p>3)
5 x의 계수(a)
11 상수항(b)
y2 = x3 + ax + b (mod p)를 만족하는 (항등원인 무한원점 (항등,원) 포함)개의 점들이 가환군을 이룸
단, 점의 수가 300개가 넘으면 필자가 힘듬이로.....
모든 원소를 찾은 것이 아님.
1(0,37),2(0,60),3(3,21),4(3,76),5(4,17),6(4,80),7(5,8),8(5,89),9(7,1),10(7,96),11(9,3),12(9,94),13(10,24),14(10,73),15(12,21),16(12,76),17(14,20),18(14,77),19(15,39),20(15,58),21(16,4),22(16,93),23(17,16),24(17,81),25(18,4),26(18,93),27(21,29),28(21,68),29(22,14),30(22,83),31(25,12),32(25,85),33(29,2),34(29,95),35(30,1),36(30,96),37(31,9),38(31,88),39(34,43),40(34,54),41(36,44),42(36,53),43(39,8),44(39,89),45(40,26),46(40,71),47(41,48),48(41,49),49(43,22),50(43,75),51(47,45),52(47,52),53(49,27),54(49,70),55(51,30),56(51,67),57(52,36),58(52,61),59(53,8),60(53,89),61(57,5),62(57,92),63(60,1),64(60,96),65(63,4),66(63,93),67(68,42),68(68,55),69(69,36),70(69,61),71(72,13),72(72,84),73(73,36),74(73,61),75(74,40),76(74,57),77(76,32),78(76,65),79(79,43),80(79,54),81(81,43),82(81,54),83(82,21),84(82,76),85(85,39),86(85,58),87(93,11),88(93,86),89(94,39),90(94,58),
-힘들다 힘들어-
타원곡선암호에서 좌표 더하기와 위수 구하기
위의 결과에서 두 개의 좌표를 골라 x, y좌표를 따로 따로 입력하세요.
0, 37 (x1좌표, y1좌표)
85, 58 (x2좌표, y2좌표)
위 좌표의 덧셈은 (0,37) + (85,58) = (9,3) 이고 좌표(0,37) 의 법 에 관한 위수(order)는 91 입니다.
계산 힘들어...
♡ 타원곡선암호에서 암호화하기
다음은 타원곡선을 이용한 ElGamal암호계입니다.
암호 알고리즘은 다음과 같습니다.
1. 수신자와 송신자는 타원곡선상 점을 누구나 구할 수 있도록 p, a, b를 공개합니다.
2. 받는 사람은 비밀키 k(정수)와 타원곡선상의 한 점 G를 선정하여 (비밀키k)*(공개키G) = kG를 계산하여 kG를 공개키로 공개합니다.
3. 보내는 사람은 평문M(타원곡선상의 점)과 암호화시 사용할 임의수 c(정수)를 선정합니다.
그리고, c와 공개키 kG를 이용하여 암호문 (C1, C2), 단,
C1 = (임의수c)*(공개키G)= cG
C2 = [(임의수c)*(비밀키k)*(공개키G)] + (평문M) = ckG + M
를 수신자에게 보냅니다.
4. 복호화는 암호문(C1,C2)를 받아 아래와 같이
C2 - (비밀키k)*C1 = [ckG + M] - k(cG) = M(평문)
으로 계산하면 평문을 얻을 수 있습니다.
받는 사람의
비밀키 k (정수) = 10
타원곡선상의 점에서 한 개의 좌표(공개키G) = 12
(x1좌표, y1좌표)(공개키G) = 76
보내는 사람의 암호화시 사용할 = 21
임의수 c (정수) = 49
(x2좌표, y2좌표)(평문M) = 27
아래는 받는 사람의 공개키인 kG = (비밀키k)*(공개키G)의 결과입니다.
10(12,76) = (76,32)
아래는 암호문C1 = cG = (임의수c)*(공개키G)의 좌표입니다.
21(12,76) = (5,8)
아래는 암호문C2 = ckG + M = [(임의수c)*(비밀키k)*(공개키G)] + (평문M)의 좌표
[21*10*(12,76)] + (49,27) = (74,57) + (49,27) = (22,83)
복호화는 암호문(C1,C2)를 받아 아래와 같이 C2 - kC1 = [ckG + M] - kcG = (평문M) 이 됨
(22,83) - 10(5,8) = (49,27)
-왠만해선 이거 안씁니다.-
(I) 체 F의 표수(characteristic)가 2와 3이 아닌 경우
체의 표수(characteristic) p 가 2와 3이 아닐 때는, 위 타원곡선을 적당히 이동을 하면 y2 = x3 + a*x + b 형태로 나온다. 이 때 암호론에서 사용하는 곡선은 변형된 타원곡선이 smooth인 경우, 즉 우변의 방정식이 중근(4*a3+27*b2 ≡0(mod p) 이면 중근존재)을 갖지 않을 경우에, 변형된 타원곡선 상의 점과 무한 원점(0)(항등원)으로 구성된 점들 사이에 적당한 덧셈연산을 정의하면 가환군이 된다는 것을 이용한 암호방법이다. 곡선상의 점 P=(x1, y1), Q=(x2, y2)의 덧셈연산은 아래 그림과 같이 두 점 P,Q를 지나는 직선과 타원곡선과 만나는 제3의 교점(x,y)을 x축에 관해 대칭한 점(x, -y)을 P+Q=(x3, y3) 로 정의한다. 계산을 해보면 아래(1)(2)와 같다. 제3의 교점이 없으면, 즉 직선이 y축과 평행하면 (3)과 같이 정의한다.
단, P + Q = (x1, y1) + (x2, y2) = (x3, y3)
(1) (x1 ≠x2)인 경우 (지나는 직선이 y축에 평행하지 않음)
x3 = (y2-y1 / x2-x1)2 - x1-x2 ; y3 = (y2-y1 / x2-x1)(x1-x3) - y1.
(2) (x1 = x2 이고 y1 = y2 ≠0)인 경우 (지나는 직선이 접선)
x3 = (3x12+a / 2y1)2 - x1-x2 ; y3 = (3x12+a / 2y1)(x1-x3) - y1.
(3) (x1 = x2 이고 y1 = -y2)인 경우 (지나는 직선이 y축에 평행)
P + Q = 0(무한원점). 즉, Q = -(x1, y1) = (x1, -y1).
P + 0(무한원점) = P.
(II) 체 F의 표수(characteristic)가 2 경우
이 경우의 체의 원소수는 2p (단 p 는 양의 정수)인 유한체가 되므로, 타원곡선은 다음 중 어느 하나와 동형이 된다.
♡ y2 + y = x3.
♡ y2 + xy = x3 + x.
♡ y2 + y = x3 + x + 1.
여기서는 간단히 계산하기 위해 y2 + y = x3 을 사용하여 덧셈연산을 한 것을 나열한다.
(1) (x1 ≠x2)인 경우 (지나는 직선이 y축에 평행하지 않음)
x3 = (y2+y1 / x2+x1)2 + x1+x2 ; y3 = (y2+y1 / x2+x1)(x1+x3) + y1 + 1.
(2) (x1 = x2 이고 y1 = y2)인 경우
x3 = x14 ; y3 = y14 + 1.
(III) 체 F의 표수(characteristic)가 3인 경우
500 이하의 다음 소수를 이용하여 연습해보기 바란다. 아래 연습에서 수의 입력 방법에 따라 이상한 결과가 나오면 왜 그런지 이유를 생각해 볼 것.
5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
♡ 타원곡선(Elliptic curve)상의 점 찾기
타원곡선 y2 = x3 + ax + b (mod p)의 연습입니다. p>3이고 4a3 + 27b2 ≡0(mod p)(중근)이 아닌 a,b 쌍을 대입하세요.
97 소수(p>3)
5 x의 계수(a)
11 상수항(b)
y2 = x3 + ax + b (mod p)를 만족하는 (항등원인 무한원점 (항등,원) 포함)개의 점들이 가환군을 이룸
단, 점의 수가 300개가 넘으면 필자가 힘듬이로.....
모든 원소를 찾은 것이 아님.
1(0,37),2(0,60),3(3,21),4(3,76),5(4,17),6(4,80),7(5,8),8(5,89),9(7,1),10(7,96),11(9,3),12(9,94),13(10,24),14(10,73),15(12,21),16(12,76),17(14,20),18(14,77),19(15,39),20(15,58),21(16,4),22(16,93),23(17,16),24(17,81),25(18,4),26(18,93),27(21,29),28(21,68),29(22,14),30(22,83),31(25,12),32(25,85),33(29,2),34(29,95),35(30,1),36(30,96),37(31,9),38(31,88),39(34,43),40(34,54),41(36,44),42(36,53),43(39,8),44(39,89),45(40,26),46(40,71),47(41,48),48(41,49),49(43,22),50(43,75),51(47,45),52(47,52),53(49,27),54(49,70),55(51,30),56(51,67),57(52,36),58(52,61),59(53,8),60(53,89),61(57,5),62(57,92),63(60,1),64(60,96),65(63,4),66(63,93),67(68,42),68(68,55),69(69,36),70(69,61),71(72,13),72(72,84),73(73,36),74(73,61),75(74,40),76(74,57),77(76,32),78(76,65),79(79,43),80(79,54),81(81,43),82(81,54),83(82,21),84(82,76),85(85,39),86(85,58),87(93,11),88(93,86),89(94,39),90(94,58),
-힘들다 힘들어-
타원곡선암호에서 좌표 더하기와 위수 구하기
위의 결과에서 두 개의 좌표를 골라 x, y좌표를 따로 따로 입력하세요.
0, 37 (x1좌표, y1좌표)
85, 58 (x2좌표, y2좌표)
위 좌표의 덧셈은 (0,37) + (85,58) = (9,3) 이고 좌표(0,37) 의 법 에 관한 위수(order)는 91 입니다.
계산 힘들어...
♡ 타원곡선암호에서 암호화하기
다음은 타원곡선을 이용한 ElGamal암호계입니다.
암호 알고리즘은 다음과 같습니다.
1. 수신자와 송신자는 타원곡선상 점을 누구나 구할 수 있도록 p, a, b를 공개합니다.
2. 받는 사람은 비밀키 k(정수)와 타원곡선상의 한 점 G를 선정하여 (비밀키k)*(공개키G) = kG를 계산하여 kG를 공개키로 공개합니다.
3. 보내는 사람은 평문M(타원곡선상의 점)과 암호화시 사용할 임의수 c(정수)를 선정합니다.
그리고, c와 공개키 kG를 이용하여 암호문 (C1, C2), 단,
C1 = (임의수c)*(공개키G)= cG
C2 = [(임의수c)*(비밀키k)*(공개키G)] + (평문M) = ckG + M
를 수신자에게 보냅니다.
4. 복호화는 암호문(C1,C2)를 받아 아래와 같이
C2 - (비밀키k)*C1 = [ckG + M] - k(cG) = M(평문)
으로 계산하면 평문을 얻을 수 있습니다.
받는 사람의
비밀키 k (정수) = 10
타원곡선상의 점에서 한 개의 좌표(공개키G) = 12
(x1좌표, y1좌표)(공개키G) = 76
보내는 사람의 암호화시 사용할 = 21
임의수 c (정수) = 49
(x2좌표, y2좌표)(평문M) = 27
아래는 받는 사람의 공개키인 kG = (비밀키k)*(공개키G)의 결과입니다.
10(12,76) = (76,32)
아래는 암호문C1 = cG = (임의수c)*(공개키G)의 좌표입니다.
21(12,76) = (5,8)
아래는 암호문C2 = ckG + M = [(임의수c)*(비밀키k)*(공개키G)] + (평문M)의 좌표
[21*10*(12,76)] + (49,27) = (74,57) + (49,27) = (22,83)
복호화는 암호문(C1,C2)를 받아 아래와 같이 C2 - kC1 = [ckG + M] - kcG = (평문M) 이 됨
(22,83) - 10(5,8) = (49,27)
-왠만해선 이거 안씁니다.-
llllllllllll 1Gbps Line