 |
|
| Science Forum Index » Cryptography Forum » Question on mathematics of ECC scheme |
|
Page 1 of 1 |
|
| Author |
Message |
| Justin |
 Posted: Mon Dec 15, 2003 3:37 pm |
|
|
|
Guest
|
In my Cryptography class, we were given free reign to choose a topic
that interests us and perform what amounts to an independent study. I
chose identity-based encryption, implementing the Identity Based
Encrytion scheme proposed in the Boneh and Franklin paper published in
Crypto '2001, and on the Web at
http://crypto.stanford.edu/~dabo/papers/ibe.pdf.
I have implemented basic elliptical curve mathematical functions
modulo some number p, as well as the Miller-Rabin test to generate a
k-bit prime number, but I am slightly confused about the generation of
the two groups G1 and G2 by the BDH Parameter Generator (page 19).
In short, I am unclear on how to generate G1 and G2.
What exactly goes into these groups? I have generated the q, found
the smallest prime p such that p=2 mod 3, q divides P+1, and q^2 does
not divide p+1. I am unclear on what is meant by the 'subgroup of
order q of the group of points on the curve over Fp'. Is it necessary
to simply try all integer values of X (0,1,2,...), check if it
satisfies the curve equation, then choose the first q of these? Since
p is less than q, how can there be a group of order q over the field
Fp?
On page 23, 'let P be some generator of G1', how do i go about finding
said P?
I appreciate your time, and I apologize if the questions seem
simplistic.
-Justin |
|
|
| Back to top |
|
|
|
| Kristian Gjøsteen |
| Posted: Mon Dec 15, 2003 11:40 pm |
|
|
|
Guest
|
In article <42ebfb41.0312151237.78fecf04@posting.google.com>,
Justin <freetek@yahoo.com> wrote:
[quote:0ec1783e22]http://crypto.stanford.edu/~dabo/papers/ibe.pdf.
I have implemented basic elliptical curve mathematical functions
modulo some number p, as well as the Miller-Rabin test to generate a
k-bit prime number, but I am slightly confused about the generation of
the two groups G1 and G2 by the BDH Parameter Generator (page 19).
In short, I am unclear on how to generate G1 and G2.
What exactly goes into these groups? I have generated the q, found
the smallest prime p such that p=2 mod 3, q divides P+1, and q^2 does
not divide p+1. I am unclear on what is meant by the 'subgroup of
order q of the group of points on the curve over Fp'.
[/quote:0ec1783e22]
When p is congruent to 2 modulo 3, the elliptic curve y^2=x^3+1 has
p+1 rational points modulo p. So the abelian group E(F_p) has order
p+1.
Since the prime q divides p+1, there is a subgroup G1 of E(F_p) of
order q. Since q^2 does not divide p+1, we know that the subgroup is
unique.
As for G2, you know that GF(p^2)* has order p^2-1=(p+1)(p-1). Again,
since q divides p+1, you know that there is a subgroup of order q.
You also know that q does not divide p-1, so when you use the Weil
pairing to move points in the q-order subgroup of E(F_p) into
GF(p^2)*, you know that the resulting element isn't in GF(p). Which
is nice.
[quote:0ec1783e22]On page 23, 'let P be some generator of G1', how do i go about finding
said P?
[/quote:0ec1783e22]
You find a generator for G1 by finding a random point P' on the curve
(perhaps (0,1) would work) and computing P=((p+1)/q)P'. If q is a large
prime, then P is, except with negligible probability, a point of order
q, and therefore it generates G1. If you happen to get zero, choose a
new random point P' and try again.
--
Kristian Gjøsteen |
|
|
| Back to top |
|
|
|
| Marcel Martin |
| Posted: Tue Dec 16, 2003 9:39 am |
|
|
|
Guest
|
Justin a écrit :
[quote:b5aa316d51]
In my Cryptography class, we were given free reign to choose a topic
that interests us and perform what amounts to an independent study. I
chose identity-based encryption, implementing the Identity Based
Encrytion scheme proposed in the Boneh and Franklin paper published in
Crypto '2001, and on the Web at
http://crypto.stanford.edu/~dabo/papers/ibe.pdf.
I have implemented basic elliptical curve mathematical functions
modulo some number p, as well as the Miller-Rabin test to generate a
k-bit prime number, but I am slightly confused about the generation of
the two groups G1 and G2 by the BDH Parameter Generator (page 19).
In short, I am unclear on how to generate G1 and G2.
What exactly goes into these groups? I have generated the q, found
the smallest prime p such that p=2 mod 3, q divides P+1, and q^2 does
not divide p+1. I am unclear on what is meant by the 'subgroup of
order q of the group of points on the curve over Fp'. Is it necessary
to simply try all integer values of X (0,1,2,...), check if it
satisfies the curve equation, then choose the first q of these? Since
p is less than q, how can there be a group of order q over the field
Fp?
On page 23, 'let P be some generator of G1', how do i go about finding
said P?
I appreciate your time, and I apologize if the questions seem
simplistic.
[/quote:b5aa316d51]
If you chose your project at random, you are not lucky. It is not
difficult to find something easier :-)
G1 is a group of points on an elliptic curve over F(p).
G2 is a subgroup of the multiplicative group of F(p^2) [*]
[*] Computationally, the elements of F(p^2) can be represented
with couples of integers mod p. Very roughly, you can use a polynomial
representation, i.e., each couple (a,b) represents the polynomial
aX + b mod p and all the computations are done modulo an irreducible
polynomial X^2 + mX + n mod p, or you can use quadratic integers, i.e.,
(a,b) represent the quadratic integer a + b*w.
For instance, here, you can represent F(p^2) with the Eisenstein
integers Z[j] mod p, i.e., a + bj mod p, where j is defined by
j^2 + j + 1 = 0 (this polynomial has no roots mod p because
(p odd prime) and (p = 2 mod 3) --> (Jacobi(-3,p) = -1)).
Defining G1.
Since the curve is Y^2 = X^3 + 1 mod p (with p = 2 mod 3, q prime, q
divides p+1 and q^2 doesn't divide p+1) to get a random point on this
curve, take a random y in F(p) and compute x := (y^2 - 1)^((2p-1)/3)
modulo p. The point (x,y) belongs to the curve. Now, compute
(u,v) := (x,y)*((p+1)/q), if (u,v) is not the Identity point then its
order is q (since, by construction, the order of the curve is p+1) and
it generates the subgroup G1. That's why G1 is called
[quote:b5aa316d51]'subgroup of order q of the group of points on the curve over Fp'.
[/quote:b5aa316d51]
For instance, let's say p = 29 and q = 5.
The curve y^2 = x^3 + 1 mod 29 has order m = p+1 = 30.
G1 = {Identity, (8,7), (8,-7), (4,23), (4,-23)} and P in G1 implies
P*5 = Identity. Since 5 is prime, any element of G1 different
from Identity is a generator of G1.
Defining G2.
Do as explained page 19 of the paper you quoted (btw, there is a typo
line 22, read p = lq - 1 and not p = lq + 1). A generator g of G2 is
given by g := e'(P,P) = e(P,phi(P)) with P a point that generates G1.
(phi being the function defined in the paper).
You could also build G2 this way.
Take a and b (mod p) at random.
Define j as j^2 + j + 1 = 0.
Compute (u + vj) := (a + bj)^((p^2-1)/q) mod p. If (u + vj) is
different from (1 + 0j) then it is a generator of order q, i.e.,
it generates a subgroup of order q in the multiplicative group of
F(p^2)).
Using p = 29 and q = 5. Take a random Eiseinstein integer mod 29,
for instance 6 + 19j. It comes
(6 + 19j)^((29*29 - 1)/5) = (-5 + 14j) mod 29 and
(-5 + 14j)^5 = 1 mod 29.
Thus (-5 + 14j) is a generator of G2.
But you will still have to compute the map e' as required in the
paper. No, you didn't choose something completely trivial :-)
I strongly advise you to work with very small numbers to write
your program (and to use bigger ones later). This way you can
exhaustively list the elements of the different sets and you can
'see' what happens.
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
|
|
| Marcel Martin |
| Posted: Wed Dec 17, 2003 1:39 pm |
|
|
|
Guest
|
Marcel Martin a écrit :
[quote:3ebb3c3c41][...]
For instance, here, you can represent F(p^2) with the Eisenstein
integers Z[j] mod p, i.e., a + bj mod p, where j is defined by
[...]
Using p = 29 and q = 5. Take a random Eiseinstein integer mod 29,
for instance 6 + 19j.
[...][/quote:3ebb3c3c41]
I wrote twice 'Eisenstein integer mod 29'. Strictly speaking, this is
wrong. What I mean is 'Eisenstein integers of which the "coefficients"
are reduced modulo 29'. That's not the same.
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
|
|
| Marcel Martin |
| Posted: Wed Dec 17, 2003 7:31 pm |
|
|
|
Guest
|
Marcel Martin a écrit :
[quote:e0e9cd7aae][...]
For instance, here, you can represent F(p^2) with the Eisenstein
integers Z[j] mod p, i.e., a + bj mod p, where j is defined by
[...]
Using p = 29 and q = 5. Take a random Eiseinstein integer mod 29,
for instance 6 + 19j.
[...]
I wrote twice 'Eisenstein integer mod 29'. Strictly speaking, this is
wrong. What I mean is 'Eisenstein integers of which the "coefficients"
^[/quote:e0e9cd7aae]
not
[quote:e0e9cd7aae]are reduced modulo 29'. That's not the same.
[/quote:e0e9cd7aae]
I agree that's totally confused. In short, the 'mod' operator used for
the computations over F(p^2) IS NOT the same than the one used for the
computations over F(p), i.e., (a + bj) mod p =/= (a mod p) + (b mod p)j.
I wanted to point out this difference in my previous mail because
someone asked me the question off list.
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Feb 08, 2010 6:10 pm
|
|