Example Of Elliptic Curve
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Example Of Elliptic Curve as PDF for free.
More details
- Words: 1,056
- Pages: 7
1 Example Of Elliptic Curve And Cryptography A.Chillali FST Of FES R´esum´e: Une courbe elliptique E (d´efinie sur un corps K), not´ee E(K), est une courbe projective non singuli`ere de genre 1 qui poss`ede un point Krationnel Ω . Toute courbe elliptique E(K) est donn´ee par une ´equation de Weierstrass : (∗)y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 . o` u ai ∈ K; i=1,2,3,4,6 . Le point Ω[0, 1, 0] est le point `a l’infini. Soient M(x1 , y1 ),N(x2 , y2 )et R(x3 , y3 ) trois points de la courbe (E) tels que R=N+M. Alors : 1) R = Ω pour x1 = x2 et y2 = −y1 − a1 x1 − a3 2) x3 = t2 + a1 t − a2 − x1 − x2 et y3 = −(t + a1 )x3 − s − a3 avec : ( y −y 2 1 ; si M6=N x2 −x1 t= 3x21 +2a1 x1 +a4 −a1 y1 ; si M=N 2y1 +a1 x1 +a3 ( s=
y1 x2 −y2 x1 ; si M6=N x2 −x1 −x31 +a4 x1 +2a6 −a3 y1 ; si 2y1 +a1 x1 +a3
M=N
Dans cet article, on repr´esente un exemple de cryptographie bas´e sur la courbe elliptique d’´equation : y 2 = x3 + 70x + 57[73].
1
Introduction
An elliptic curve is a pair (E, Ω), where E is a smooth projective curve of genus 1 and Ω is a point of E, called the point at infinity. In this paper, we present a elliptic curve can be given by a Weierstrass equation: y 2 = x3 + 70x + 57[73]. A curve contains 74 points.
2
2
Coding of the curve points curve Point [3, 41] [66, 10] [45, 4] [60, 4] [47, 58] [21, 35] [41, 69] [53, 72] [42, 56] [64, 31] [29, 59] [35, 66] [19, 56] [63, 67] [11, 48] [13, 5] [32, 5] [26, 53] [52, 35] [50, 2] [4, 67] [12, 17] [57, 30] [1, 37] [0, 38] [71, 37] [23, 16] [44, 65] [22, 28] [24, 31] [55, 22] [38, 49] [28, 68] [58, 31]
code Symbol 000001101010010000001 a 100001000010100000001 b 010110100001000000001 c 011110000001000000001 d 010111101110100000001 e 001010101000110000001 f 010100110001010000001 g 011010110010000000001 h 010101001110000000001 i 100000000111110000001 j 001110101110110000001 k 010001110000100000001 l 001001101110000000001 m 011111110000110000001 n 000101101100000000001 o 000110100001010000001 p 010000000001010000001 q 001101001101010000001 r 011010001000110000001 s 011001000000100000001 t 000010010000110000001 u 000110000100010000001 v 011100100111100000001 w 000000101001010000001 x 000000001001100000001 y 100011101001010000001 z 001011100100000000001 A 010110010000010000001 B 001011000111000000001 C 001100000111110000001 D 011011100101100000001 E 010011001100010000001 F 001110010001000000001 G 011101000111110000001 H
3 Curve Point [6, 6] [46, 47] [62, 0] [46, 26] [6, 67] [58, 42] [28, 5] [38, 24] [55, 51] [24, 42] [22, 45] [44, 8] [23, 57] [71, 36] [0, 35] [1, 36] [57, 43] [12, 56] [4, 6] [50, 71] [52, 38] [26, 20] [32, 68] [13, 68] [11, 25] [63, 6] [19, 17] [35, 7] [64, 42] [64, 42] [42, 17] [53, 1] [41, 4] [21, 38] [47, 15] [60, 69] [45, 69] [66, 63] [3, 32] Ω
code Symbol 000011000001100000001 I 010111001011110000001 J 011111000000000000001 K 010111000110100000001 L 000011010000110000001 M 011101001010100000001 N 001110000001010000001 O 010011000110000000001 P 011011101100110000001 Q 001100001010100000001 R 001011001011010000001 S 010110000010000000001 T 001011101110010000001 U 100011101001000000001 V 000000001000110000001 W 00000101001000000001 X 011100101010110000001 Y 000110001110000000001 Z 000010000001100000001 0 011001010001110000001 1 011010001001100000001 2 001101000101000000001 3 010000010001000000001 4 000110110001000000001 5 000110110001000000001 6 011111100001100000001 7 001001100100010000001 8 001001100100010000001 9 010001100001110000001 / 001110100011100000001 @ 100000001010100000001 ´e 010101000100010000001 `e 011010100000010000001 u ` 010100100001000000001 a` 001010101001100000001 . 010111100011110000001 , 011110010001010000001 ; 010110110001010000001 + 100001001111110000001 000000000000010000001 ?
4
3
Crypting
Let’s crypt the message m with A, which will be sent to B. A has chosen the elliptic curve (E) and The generator point P [3, 41]. (we can choose another generator point if it exists). Example m:=”Bonjour” A transforms the message m to the following message with reference to the table. ”10000100001010000000100010110110000000000101111111000011000000110000000 0111110000001000101101100000000001000010010000110000001001101001101010000001” It sends the message to B n:=”100100111000110011100100000110101001000000110000100001010000000100010 1101100000000001011111110000110000001100000000111110000001000101101100000000 00100001001000011000000100110100110101000000101001001”
4
Decrypting
B receives the message from A, it knows that A has used an elliptic curve which must find p, a, b et the generator point respectively. It reads its message from the first symbol towards the last and from the last to the first alternatively until it finds two different symbols, it’s the point p=1001001=73 as it is found. It restarts the reading in a normal way, it finds a=1000110=70 and b=0111001=57. Now, B knows that the points of the elliptic curve (E) have a 21 bits code and the first 21 bits of the message is the generator point P of the group. It is the point which represents the letter a, as well as 2P represents the letter b ....74P represents ?. So B finds n, it is exactly ”Bonjour” after transformation.
5
Implementation
>chiffrement:= proc(message) local taille,resultat,i,num; num := table(["a"="000001101010010000001","b"="100001000010100000001","c"="01 0110100001000000001","d"="011110000001000000001","e"="0101111011101000 00001","f"="001010101000110000001","g"="010100110001010000001","h"="01 1010110010000000001","i"="010101001110000000001","j"="1000000001111100 00001","k"="001110101110110000001","l"="010001110000100000001","m"="00 1001101110000000001","n"="011111110000110000001","o"="0001011011000000
5 00001","p"="000110100001010000001","q"="010000000001010000001","r"="00 1101001101010000001","s"="011010001000110000001","t"="0110010000001000 00001","u"="000010010000110000001","v"="000110000100010000001","w"="01 1100100111100000001","x"="000000101001010000001","y"="0000000010011000 00001","z"="100011101001010000001","A"="001011100100000000001","B"="01 0110010000010000001","C"="001011000111000000001","D"="0011000001111100 00001","E"="011011100101100000001","F"="010011001100010000001","G"="00 1110010001000000001","H"="011101000111110000001","I"="0000110000011000 00001","J"="010111001011110000001","K"="011111000000000000001","L"="01 0111000110100000001","M"="000011010000110000001","N"="0111010010101000 00001","O"="001110000001010000001","P"="010011000110000000001","Q"="01 1011101100110000001","R"="001100001010100000001","S"="0010110010110100 00001","T"="010110000010000000001" ,"U"="001011101110010000001","V"="100011101001000000001","W"="00000000 1000110000001","X"="000000101001000000001","Y"="011100101010110000001" ,"Z"="000110001110000000001", "/"="001110100011100000001",","="011110010001010000001","?"="000000000 000010000001",";"="010110110001010000001","."="010111100011110000001", "0"="000010000001100000001","1"="011001010001110000001","2"="011010001 001100000001","3"="001101000101000000001","4"="010000010001000000001", "5"="000110110001000000001","6"="001100100010110000001","7"="011111100 001100000001","8"="001001100100010000001","9"="010001100001110000001", "´ e"="010101000100010000001","` e"="011010100000010000001"," a `"="001010101001100000001","+"="100001001111110000001","` u"="0101001000 01000000001","@"="100000001010100000001","-"="000001101000000000001"]) : if not type(message,string) then ERROR("le message doit etre une chaine de caracteres") fi; taille := length(message); resultat:=""; if taille = 0 then RETURN("") fi; for i from 1 to taille do resultat := cat(resultat,num[substring(message,i..i)]); od; end: >a:=chiffrement("Bonjour"); a := "010110010000010000001000101101100000000001011111110000110000001100000 0001111100000010001011011000000000010000100100001100000010011010011010 10000001" >dechiffrement := proc(message)
6 local taille,resultat,i,num; num := table(["000001101010010000001"="a","100001000010100000001"="b","01011 0100001000000001"="c","011110000001000000001"="d","0101111011101000000 01"="e","001010101000110000001"="f","010100110001010000001"="g","01101 0110010000000001"="h","010101001110000000001"="i","1000000001111100000 01"="j","001110101110110000001"="k","010001110000100000001"="l","00100 1101110000000001"="m","011111110000110000001"="n","0001011011000000000 01"="o","000110100001010000001"="p","010000000001010000001"="q","00110 1001101010000001"="r","011010001000110000001"="s","0110010000001000000 01"="t","000010010000110000001"="u","000110000100010000001"="v","01110 0100111100000001"="w","000000101001010000001"="x","0000000010011000000 01"="y","100011101001010000001"="z","001011100100000000001"="A","01011 0010000010000001"="B","001011000111000000001"="C","0011000001111100000 01"="D","011011100101100000001"="E","010011001100010000001"="F","00111 0010001000000001"="G","011101000111110000001"="H","0000110000011000000 01"="I","010111001011110000001"="J","011111000000000000001"="K","01011 1000110100000001"="L","000011010000110000001"="M","0111010010101000000 01"="N","001110000001010000001"="O","010011000110000000001"="P","01101 1101100110000001"="Q","001100001010100000001"="R","0010110010110100000 01"="S","010110000010000000001"="T" ,"001011101110010000001"="U","100011101001000000001"="V","000000001000 110000001"="W","000000101001000000001"="X","011100101010110000001"="Y" ,"000110001110000000001"="Z", "001110100011100000001"="/","011110010001010000001"=",","0000000000000 10000001"="?","010110110001010000001"=";","010111100011110000001"=".", "000010000001100000001"="0","011001010001110000001"="1","0110100010011 00000001"="2","001101000101000000001"= "3","010000010001000000001"="4","000110110001000000001"="5","001100100 010110000001"="6","011111100001100000001"="7","001001100100010000001"= "8","010001100001110000001"="9", "010101000100010000001"="´ e","011010100000010000001"=" e `","001010101001100000001"=" a `","100001001111110000001"="+","010100100001000000001"="` u","1000000010 10100000001"="@","000001101000000000001"="-"]): if not type(message,string) then ERROR("le message doit etre une chaine de caracteres") fi; taille := length(message)/21; resultat:=""; if taille = 0 then RETURN("") fi; for i from 1 to taille do
7 resultat := cat(resultat,num[substring(message,((i-1)*21)+1..((i-1)*21)+21)]); od; end: >dechiffrement(a); "Bonjour"
References [1] A. Menezes, T. Okamoto, S. Vanstone :Reducing elliptic curve logarithms to logarithms in a field,in proceedings of the twenty third annual ACM symposium on theory of computing,p.80-89,ACM Press, 1991. [2] A. Nitaj:Le probl`eme du logarithme discret elliptique Index et Xedni. Mathematics subject classification. 11G20, 11Y16. April 2001. [3] A. Joux, R. Lercier:Algorithmes pour r´esoudre le probl`eme du logarithme discret dans les corps finis, Nouvelles m´ethodes math´ematiques en cryptographie, facicule journ´ees annueles, page 23-53 juin 2007. [4] E. Peyre:Corps finis et courbes elliptiques, 13 septembre 2007.
y1 x2 −y2 x1 ; si M6=N x2 −x1 −x31 +a4 x1 +2a6 −a3 y1 ; si 2y1 +a1 x1 +a3
M=N
Dans cet article, on repr´esente un exemple de cryptographie bas´e sur la courbe elliptique d’´equation : y 2 = x3 + 70x + 57[73].
1
Introduction
An elliptic curve is a pair (E, Ω), where E is a smooth projective curve of genus 1 and Ω is a point of E, called the point at infinity. In this paper, we present a elliptic curve can be given by a Weierstrass equation: y 2 = x3 + 70x + 57[73]. A curve contains 74 points.
2
2
Coding of the curve points curve Point [3, 41] [66, 10] [45, 4] [60, 4] [47, 58] [21, 35] [41, 69] [53, 72] [42, 56] [64, 31] [29, 59] [35, 66] [19, 56] [63, 67] [11, 48] [13, 5] [32, 5] [26, 53] [52, 35] [50, 2] [4, 67] [12, 17] [57, 30] [1, 37] [0, 38] [71, 37] [23, 16] [44, 65] [22, 28] [24, 31] [55, 22] [38, 49] [28, 68] [58, 31]
code Symbol 000001101010010000001 a 100001000010100000001 b 010110100001000000001 c 011110000001000000001 d 010111101110100000001 e 001010101000110000001 f 010100110001010000001 g 011010110010000000001 h 010101001110000000001 i 100000000111110000001 j 001110101110110000001 k 010001110000100000001 l 001001101110000000001 m 011111110000110000001 n 000101101100000000001 o 000110100001010000001 p 010000000001010000001 q 001101001101010000001 r 011010001000110000001 s 011001000000100000001 t 000010010000110000001 u 000110000100010000001 v 011100100111100000001 w 000000101001010000001 x 000000001001100000001 y 100011101001010000001 z 001011100100000000001 A 010110010000010000001 B 001011000111000000001 C 001100000111110000001 D 011011100101100000001 E 010011001100010000001 F 001110010001000000001 G 011101000111110000001 H
3 Curve Point [6, 6] [46, 47] [62, 0] [46, 26] [6, 67] [58, 42] [28, 5] [38, 24] [55, 51] [24, 42] [22, 45] [44, 8] [23, 57] [71, 36] [0, 35] [1, 36] [57, 43] [12, 56] [4, 6] [50, 71] [52, 38] [26, 20] [32, 68] [13, 68] [11, 25] [63, 6] [19, 17] [35, 7] [64, 42] [64, 42] [42, 17] [53, 1] [41, 4] [21, 38] [47, 15] [60, 69] [45, 69] [66, 63] [3, 32] Ω
code Symbol 000011000001100000001 I 010111001011110000001 J 011111000000000000001 K 010111000110100000001 L 000011010000110000001 M 011101001010100000001 N 001110000001010000001 O 010011000110000000001 P 011011101100110000001 Q 001100001010100000001 R 001011001011010000001 S 010110000010000000001 T 001011101110010000001 U 100011101001000000001 V 000000001000110000001 W 00000101001000000001 X 011100101010110000001 Y 000110001110000000001 Z 000010000001100000001 0 011001010001110000001 1 011010001001100000001 2 001101000101000000001 3 010000010001000000001 4 000110110001000000001 5 000110110001000000001 6 011111100001100000001 7 001001100100010000001 8 001001100100010000001 9 010001100001110000001 / 001110100011100000001 @ 100000001010100000001 ´e 010101000100010000001 `e 011010100000010000001 u ` 010100100001000000001 a` 001010101001100000001 . 010111100011110000001 , 011110010001010000001 ; 010110110001010000001 + 100001001111110000001 000000000000010000001 ?
4
3
Crypting
Let’s crypt the message m with A, which will be sent to B. A has chosen the elliptic curve (E) and The generator point P [3, 41]. (we can choose another generator point if it exists). Example m:=”Bonjour” A transforms the message m to the following message with reference to the table. ”10000100001010000000100010110110000000000101111111000011000000110000000 0111110000001000101101100000000001000010010000110000001001101001101010000001” It sends the message to B n:=”100100111000110011100100000110101001000000110000100001010000000100010 1101100000000001011111110000110000001100000000111110000001000101101100000000 00100001001000011000000100110100110101000000101001001”
4
Decrypting
B receives the message from A, it knows that A has used an elliptic curve which must find p, a, b et the generator point respectively. It reads its message from the first symbol towards the last and from the last to the first alternatively until it finds two different symbols, it’s the point p=1001001=73 as it is found. It restarts the reading in a normal way, it finds a=1000110=70 and b=0111001=57. Now, B knows that the points of the elliptic curve (E) have a 21 bits code and the first 21 bits of the message is the generator point P of the group. It is the point which represents the letter a, as well as 2P represents the letter b ....74P represents ?. So B finds n, it is exactly ”Bonjour” after transformation.
5
Implementation
>chiffrement:= proc(message) local taille,resultat,i,num; num := table(["a"="000001101010010000001","b"="100001000010100000001","c"="01 0110100001000000001","d"="011110000001000000001","e"="0101111011101000 00001","f"="001010101000110000001","g"="010100110001010000001","h"="01 1010110010000000001","i"="010101001110000000001","j"="1000000001111100 00001","k"="001110101110110000001","l"="010001110000100000001","m"="00 1001101110000000001","n"="011111110000110000001","o"="0001011011000000
5 00001","p"="000110100001010000001","q"="010000000001010000001","r"="00 1101001101010000001","s"="011010001000110000001","t"="0110010000001000 00001","u"="000010010000110000001","v"="000110000100010000001","w"="01 1100100111100000001","x"="000000101001010000001","y"="0000000010011000 00001","z"="100011101001010000001","A"="001011100100000000001","B"="01 0110010000010000001","C"="001011000111000000001","D"="0011000001111100 00001","E"="011011100101100000001","F"="010011001100010000001","G"="00 1110010001000000001","H"="011101000111110000001","I"="0000110000011000 00001","J"="010111001011110000001","K"="011111000000000000001","L"="01 0111000110100000001","M"="000011010000110000001","N"="0111010010101000 00001","O"="001110000001010000001","P"="010011000110000000001","Q"="01 1011101100110000001","R"="001100001010100000001","S"="0010110010110100 00001","T"="010110000010000000001" ,"U"="001011101110010000001","V"="100011101001000000001","W"="00000000 1000110000001","X"="000000101001000000001","Y"="011100101010110000001" ,"Z"="000110001110000000001", "/"="001110100011100000001",","="011110010001010000001","?"="000000000 000010000001",";"="010110110001010000001","."="010111100011110000001", "0"="000010000001100000001","1"="011001010001110000001","2"="011010001 001100000001","3"="001101000101000000001","4"="010000010001000000001", "5"="000110110001000000001","6"="001100100010110000001","7"="011111100 001100000001","8"="001001100100010000001","9"="010001100001110000001", "´ e"="010101000100010000001","` e"="011010100000010000001"," a `"="001010101001100000001","+"="100001001111110000001","` u"="0101001000 01000000001","@"="100000001010100000001","-"="000001101000000000001"]) : if not type(message,string) then ERROR("le message doit etre une chaine de caracteres") fi; taille := length(message); resultat:=""; if taille = 0 then RETURN("") fi; for i from 1 to taille do resultat := cat(resultat,num[substring(message,i..i)]); od; end: >a:=chiffrement("Bonjour"); a := "010110010000010000001000101101100000000001011111110000110000001100000 0001111100000010001011011000000000010000100100001100000010011010011010 10000001" >dechiffrement := proc(message)
6 local taille,resultat,i,num; num := table(["000001101010010000001"="a","100001000010100000001"="b","01011 0100001000000001"="c","011110000001000000001"="d","0101111011101000000 01"="e","001010101000110000001"="f","010100110001010000001"="g","01101 0110010000000001"="h","010101001110000000001"="i","1000000001111100000 01"="j","001110101110110000001"="k","010001110000100000001"="l","00100 1101110000000001"="m","011111110000110000001"="n","0001011011000000000 01"="o","000110100001010000001"="p","010000000001010000001"="q","00110 1001101010000001"="r","011010001000110000001"="s","0110010000001000000 01"="t","000010010000110000001"="u","000110000100010000001"="v","01110 0100111100000001"="w","000000101001010000001"="x","0000000010011000000 01"="y","100011101001010000001"="z","001011100100000000001"="A","01011 0010000010000001"="B","001011000111000000001"="C","0011000001111100000 01"="D","011011100101100000001"="E","010011001100010000001"="F","00111 0010001000000001"="G","011101000111110000001"="H","0000110000011000000 01"="I","010111001011110000001"="J","011111000000000000001"="K","01011 1000110100000001"="L","000011010000110000001"="M","0111010010101000000 01"="N","001110000001010000001"="O","010011000110000000001"="P","01101 1101100110000001"="Q","001100001010100000001"="R","0010110010110100000 01"="S","010110000010000000001"="T" ,"001011101110010000001"="U","100011101001000000001"="V","000000001000 110000001"="W","000000101001000000001"="X","011100101010110000001"="Y" ,"000110001110000000001"="Z", "001110100011100000001"="/","011110010001010000001"=",","0000000000000 10000001"="?","010110110001010000001"=";","010111100011110000001"=".", "000010000001100000001"="0","011001010001110000001"="1","0110100010011 00000001"="2","001101000101000000001"= "3","010000010001000000001"="4","000110110001000000001"="5","001100100 010110000001"="6","011111100001100000001"="7","001001100100010000001"= "8","010001100001110000001"="9", "010101000100010000001"="´ e","011010100000010000001"=" e `","001010101001100000001"=" a `","100001001111110000001"="+","010100100001000000001"="` u","1000000010 10100000001"="@","000001101000000000001"="-"]): if not type(message,string) then ERROR("le message doit etre une chaine de caracteres") fi; taille := length(message)/21; resultat:=""; if taille = 0 then RETURN("") fi; for i from 1 to taille do
7 resultat := cat(resultat,num[substring(message,((i-1)*21)+1..((i-1)*21)+21)]); od; end: >dechiffrement(a); "Bonjour"
References [1] A. Menezes, T. Okamoto, S. Vanstone :Reducing elliptic curve logarithms to logarithms in a field,in proceedings of the twenty third annual ACM symposium on theory of computing,p.80-89,ACM Press, 1991. [2] A. Nitaj:Le probl`eme du logarithme discret elliptique Index et Xedni. Mathematics subject classification. 11G20, 11Y16. April 2001. [3] A. Joux, R. Lercier:Algorithmes pour r´esoudre le probl`eme du logarithme discret dans les corps finis, Nouvelles m´ethodes math´ematiques en cryptographie, facicule journ´ees annueles, page 23-53 juin 2007. [4] E. Peyre:Corps finis et courbes elliptiques, 13 septembre 2007.
Related Documents
Example Of Elliptic Curve
May 2020 10
Elliptic Curve Cryptography
June 2020 7
Elliptic Curve Cryptography Theory
May 2020 9
