Security Forums :: View topic - Primitive element + Public crypto mathematics pointer

Primitive element + Public crypto mathematics pointer

Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

Author: Theleo, Location: GREECE/UK

Posted: Wed Mar 09, 2005 5:17 am Post subject: Primitive element + Public crypto mathematics pointer
----
What on earth is a Primitive element? Does is it have to do with coprime numbers? I have found a number of definitions but cannot get them.

On my course (infosec course) we are given the mathematical formulas of how to Implement RSA EL-Gammal but not complete deal on the underlying mathematical explanation of how the basics work. I tried a mathematical book on number theory (including modular
Arithmetic, Euclid algorithm, Repeated Squares,CRT,Fermat's LT etc) but things went bad really quick.

Given the fact that it took me on average 1 hour for understanding a page, and that what for me what difficult or impossible to prove was usually left as an exercise(ridiculously easy apparently)for the reader. I do not have a degree in mathematics and although I like them i do not have the time ( I would need at least a month if i not more) to go through a difficult to read mathematical book.

Any resources that do explain how the underlying mathematics works in simpler terms?

Thanks,

P.S Does it get even worse when i get to Elyptic curves?

Author: darkcreature,

Posted: Wed Mar 09, 2005 5:51 am Post subject:
----
I cannot explain the primitive element (yet, I have to look back in my books on the shelf) but I can explain the math in those others that you mentioned. Also, elliptical curves aren't too hard, but initially understanding fields and what not can become overwhelming.

DC

Author: data, Location: India

Posted: Wed Mar 09, 2005 8:39 am Post subject: Re: Primitive element + Public crypto mathematics pointer
----
hi,

Theleo wrote:

What on earth is a Primitive element? Does is it have to do with coprime numbers? I have found a number of definitions but cannot get them.

Co-prime and Relatively prime are the same. Usually an element is said to be primitive, if it cannot be further broken down,i.e not factorisable. Two numbers a,b are said to be co-prime if they have no factors in common.

eg, gcd(5,8)=1 i.e. no common factors and hence co-prime.
gcd(2,8)=2 ,common factor is 2, hence not co-prime.

Quote:

Fermats LT etc) but things went bad really quick.

.
There is the Fermat's Little theorem and the Fermat's Last theorem, you must decide which :)

Quote:

Given the fact that it took me on average 1 hour for understanding a page, and that what for me what difficult or impossible to prove was usually left as an exercise(ridiculously easy apparently)for the reader. I do not have a degree in mathematics and although I like them i do not have the time ( I would need at least a month if i not more) to go through a difficult to read mathematical book.

Time is what the mind makes of it. Number theory is too intriguing a subject, one page per hour is good! If you are intrested in it you should consider spending lots of time learning it. There is no other easy way.

Quote:

Any resources that do explain how the underlying mathematics works in simpler terms?

I would recommend this book.

Quote:

P.S Does it get even worse when i get to Elyptic curves?

Its elliptic curves. You don't need a math degree to understand all the math you need, just lots of patience and persistence.

Cheers,
Data.

Author: Theleo, Location: GREECE/UK

Posted: Fri Mar 11, 2005 9:57 am Post subject:
----
Hi, Thanks for replying

Probably I did not explain myself very clearly in my previous post sorry about that. I will try to elaborate more.

I know when two numbers are coprime what I do know is :what is the relation between coprime numbers and primitive element.

I ll give a mixture of what I (at least I think) know, what I presume and what I do not know.This will probably help to undestand where i am lacking knowledge at.

The first two steps when setting up El-Gammal is

A) To choose a large prime P
(Which I presume you create by two primes, because you will need knowledge of these primes in the choice of the primitive element)

B) Choose a primitive element. How do you choose it? Why it has to be co prime with P?

Can you please be more specific about?

Quote:

Datah said:
Usually an element is said to be primitive, if it cannot be further broken down, i.e not factorisable

Quote:

Datah said:
There is the Fermat's Little theorem and the Fermat's Last theorem, you must decide which Smile

I meant Fermat’s little theorem I am not aware of any practical use of Fermat’s last theorem in cryptography.Thanks for the book suggestion I will probably invest on it after I finish my exams.

Thanks Theleo

Author: data, Location: India

Posted: Fri Mar 11, 2005 11:19 am Post subject:
----
hi,

Quote:

The first two steps when setting up El-Gammal is

A) To choose a large prime P
(Which I presume you create by two primes, because you will need knowledge of these primes in the choice of the primitive element)

B) Why it has to be co prime with P?

The scheme of El-gamal starts like this:
You generate a large prime p using a suitable primality test such as Miller-Rabin test.

Choose two numbers g and x less than they are less than p.

First, we note that all numbers between 1 and p are co-prime to p. This is because p has only two factors, 1 and the number itself.
Therefore, gcd(0<some_number<p , p)=1.

In this case, the conept of a primitive element is different from what I earlier mentioned.

We say that g is primitive to p, if g is a generator
with respect to p.

It means that g^i(mod p) will generate all the numbers between 0 and p-1 for 0<i<p.

As an example.

Code:

We check if 2 is a generator with respect to the prime number 19.
Let == indicate the linear congruence.

2^1==2 mod 19
2^2==4 mod 19
2^3==8 mod 19
2^4==16 mod 19
2^5==13 mod 19
2^6==7 mod 19
2^7==14 mod 19
2^8==9 mod 19
2^9==18 mod 19
2^10==17 mod 19
2^11==15 mod 19
2^12==11 mod 19
2^13==3 mod 19
2^14==6 mod 19
2^15==12 mod 19
2^16= =5 mod 19
2^17== 10 mod 19
2^18==1 mod 19

We see it generates the sequence
{2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10,1}

Hence 2 is a generator w.r.t 19. However all numbers between 0 and p-1 need not be generators.

Quote:

Choose a primitive element. How do you choose it?

To choose a generator g w.r.t to p we do the following:

1.) Find the factorization of p-1. You could probably use
this for factoring.

2.) p-1= q1*q2*…*qn , the prime factors of p-1

3.) Then we find
Order1 = g^(p-1)/q1
Order2 = g^(p-1)/q2
Order3 = g^(p-1)/q3
Order4 = g^(p-1)/q4
Order5 = g^(p-1)/q5
. . . . . . . . . . . .
. . . . . . . . . . . .
Ordern = g^(p-1)/qn

4.) For (1<=i<=n), if any of Order_i = 1, the given element is not a generator. We test another random element less than p until we find a generator.

Quote:

I meant Fermat’s little theorem I am not aware of any practical use of Fermat’s last theorem in cryptography.

Yup, what about it?

Data.

Author: Amitabh, Location: Australia

Posted: Sun Mar 13, 2005 2:42 am Post subject: generators
----
I have heard that finding generators for any random prime is a hard problem... is it true?

In the case of DSA etc, we generate q and p = 1 mod q

in this case, q is a generator of p

Author: data, Location: India

Posted: Sun Mar 13, 2005 6:58 am Post subject: Re: generators
----

Amitabh wrote:

I have heard that finding generators for any random prime is a hard problem... is it true?

There are precisely phi(p-1) generators between 0 and p. Finding one won't be hard.

q is a generator only if it is of maximum order. Any element between 0 and p has maximum order if it generates all elements between 0 and p exactly once.

Quote:

In the case of DSA etc, we generate q and p = 1 mod q
in this case, q is a generator of p

The order of any element (0<a<p) divides p-1. Hence
p= 1 mod q, doesnot necessarily make it a generator.

For e.g.
5==1 mod 4 , p=5 and q=4.

4^1 mod 5==4
4^2 mod 5==1
4^3 mod 5==4
4^4 mod 5==1

Evidently 4 is not a generator w.r.t to p=5.

Data.

Author: Amitabh, Location: Australia

Posted: Sun Mar 13, 2005 7:20 am Post subject:
----
I was wrong in the above post..
Suppose p, q are primes such that p = 1 mod q

for any random g, let h = g^((p-1)/q) mod p
if h is not equal to 1, then h is a generator of p

However finding a generator of a prime p seems to be an easier problem than finding a prime q < p such that p is 1 mod q. (is this true ?)

Author: data, Location: India

Posted: Sun Mar 13, 2005 11:08 am Post subject:
----

Amitabh wrote:

Suppose p, q are primes such that p = 1 mod q

for any random g, let h = g^((p-1)/q) mod p
if h is not equal to 1, then h is a generator of p

This test is incomplete. We have to test for all the factors of p-1 and not for just one factor q of p. It is also not enough to choose any two primes p,q such that p = 1 mod q.
Let me provide a counter example.

Let p=11,q=5.

11==1 mod 5 (is true)
Let g=2. Going by your test.

h=2^((11-1)/5) mod 11
=2^(10/5) mod 11
=4 mod 11=4.

therefore h=4 and not 1. The claim is that 4 is a generator w.r.t to p=11. We now verify the claim.

4^1 mod 11=4.
4^2 mod 11=5.
4^3 mod 11=9.
4^4 mod 11=3.
4^5 mod 11=1.

4^6 mod 11=4.
4^7 mod 11=5.
4^8 mod 11=9.
4^9 mod 11=3.
4^10 mod 11=1.

As we see it only generates half the numbers between 0 and 11. Hence 4 is not a generator and the claim is false.

The right way to test is as follows.

p-1=11-1=10=2*5(on factorising)

q1=2 and q2=5.

To test if 4 is a generator, we compute

Order1=4^(10/2) mod 11=1.
Order2=4^(10/5) mod 11=5.

Since Order1=1, 4 is not a generator.

Quote:

However finding a generator of a prime p seems to be an easier problem than finding a prime q < p such that p is 1 mod q. (is this true ?)

I don't think that method works but please verify for yourself.

Data.

Author: Amitabh, Location: Australia

Posted: Sun Mar 13, 2005 12:14 pm Post subject:
----

Quote:

Suppose p, q are primes such that p = 1 mod q

for any random g, let h = g^((p-1)/q) mod p
if h is not equal to 1, then h is a generator of p

Sorry, What I meant was: g is a generator of p.
Since if r = (p-1)/q and h != 1 then the only bigger order of g has to be (p-1) because q itself is prime. Thus it is enough to check if g^r = 1 mod p or not.

Thus my claim is that to find a generator of a prime p, all we need is another smaller prime q such that p = 1 mod q

(additionally, finding such a q will imply that we can factor p-1. Thus if p is large, finding generators of p is a hard problem of the order of factoring)

Edit:I am unable to prove that if we can somehow find generators of p, then we can also factor p-1.

Can anyone shed light on this? [finding generators of p is equivalent to factoring p-1: TRUE/FALSE]

Author: data, Location: India

Posted: Sun Mar 13, 2005 8:43 pm Post subject:
----

Amitabh wrote:

What I meant was: g is a generator of p.
Since if r = (p-1)/q and h != 1 then the only bigger order of g has to be (p-1) because q itself is prime. Thus it is enough to check if g^r = 1 mod p or not. Thus my claim is that to find a generator of a prime p, all we need is another smaller prime q such that p = 1 mod q

But there can be a prime smaller than q or a prime larger than q, which may cause the element under test to have a lower order or [higher order but not maximum order], thus preventing the element from being a generator. That is why we need to verify for each of the factors of p-1.

As an example.

Let q=5.We check if a=4 is a generatot w.r.t p=11.
r=(p-1)/q=(11-1)/5=2.
and g^r=4^2(mod 11)=5.
As per your test we conclude it is a generator but if we look below we see that 4 is not a generator.

4^1 mod 11=4.
4^2 mod 11=5.
4^3 mod 11=9.
4^4 mod 11=3.
4^5 mod 11=1.

4^6 mod 11=4.
4^7 mod 11=5.
4^8 mod 11=9.
4^9 mod 11=3.
4^10 mod 11=1.

The order of any element (0<a<p) divides p-1. If q be the order, then
q|(p-1) or p==1 mod q. It is just a property of elements in a multiplicative field. It doesnot imply anything more.

Quote:

(additionally, finding such a q will imply that we can factor p-1.

It implies that we have 2 and q. The other factors still needs to be determined.

Quote:

Thus if p is large, finding generators of p is a hard problem of the order of factoring

All references I know point out to the factorisation method. If that is the case, it is an NP-Hard problem.

Quote:

I am unable to prove that if we can somehow find generators of p, then we can also factor p-1.

Can anyone shed light on this? [finding generators of p is equivalent to factoring p-1: TRUE/FALSE]

False. What information of the factorisation of p-1 do we get by merely knowing the generators in it?

However finding all the subgroups generated is equivalent to determining the factorisation of p-1.

Data.

Author: Amitabh, Location: Australia

Posted: Sun Mar 13, 2005 11:48 pm Post subject:
----
Thanks for the pointer.. another thing was missing Razz

Modified algorithm:

Find prime q and p > q such that p = 1 mod q.
let r = (p-1)/q

for random g,

if (a) g ^ r mod p != 1 AND
(b) g ^ q mod p != 1

Then g is a generator.. (I missed the second test g^q != 1 mod p)

Hopefully there are no loopholes this time Very Happy

In fact thats the idea of having q prime so we dont have to worry about factors of q

I think this test will work..
the order of any such g will be the product of r and q and that is p-1

This is Lagrange's Group Theorem

(I may have misunderstood.. could the order be a product of q and a factor of r?)

Author: data, Location: India

Posted: Mon Mar 14, 2005 12:50 pm Post subject:
----

Amitabh wrote:

Modified algorithm:

Find prime q and p > q such that p = 1 mod q.
let r = (p-1)/q

for random g,

if (a) g ^ r mod p != 1 AND
(b) g ^ q mod p != 1

Then g is a generator.. (I missed the second test g^q != 1 mod p)
Hopefully there are no loopholes this time Very Happy

This trick will only work if the prime factorisation of p-1 has two prime factors.

As a counterexample, we take a p-1 whose factorisation yields three factors.

Let p=19, q=3 ,g=4(to be tested for generator).
19==1 mod 3 (is true).
r=(p-1)/q =(18/3)=6.

(a) g^r (mod p)=4^6(mod 19)=11 (not equal 1)
(b) g^q (mod p)=4^3(mod 19)=7 (not equal 1)

According to your test now 4 is a generator.We now verify if the claim is true.

4^1 (mod 19)=4
4^2 (mod 19)=16
4^3 (mod 19)=7
4^4 (mod 19)=9
4^5 (mod 19)=17
4^6 (mod 19)=11
4^7 (mod 19)=6
4^8 (mod 19)=5
4^9 (mod 19)=1

4^10 (mod 19)=4
4^11 (mod 19)=16
4^12 (mod 19)=7
4^13 (mod 19)=9
4^14 (mod 19)=17
4^15 (mod 19)=11
4^16 (mod 19)=6
4^17 (mod 19)=5
4^18 (mod 19)=1

It is clearly not a generator.

Quote:

In fact thats the idea of having q prime so we dont have to worry about factors of q

Yes, I figured that out Smile

Quote:

I think this test will work..
the order of any such g will be the product of r and q and that is p-1

This is Lagrange's Group Theorem

(I may have misunderstood.. could the order be a product of q and a factor of r?)

As per our definition r=(p-1)/q. Evidently r*q=p-1.
It can be q* a_factor_of_p-1, if p-1 has only two prime factors, namely q and a_factor_of_p-1.

Based on Lagrange's group theroem, there are some methods to generate all the subgroups in a group and thus allowing us to determine the factorisation of p-1. However you may find that all the subgroups are easily generated only for small groups with a few elements in it.

Data.

Last edited by data on Wed Apr 13, 2005 1:41 pm; edited 1 time in total

Author: data, Location: India

Posted: Wed Apr 13, 2005 1:39 pm Post subject:
----
hi,

You might like to see the Pollard's p-1 method for factorisation. It pretty much uses the idea you discussed above.

Sorry to double post, there was no other way to bring this thread up.

Data.

Author: Dark-Avenger, Location: France

Posted: Thu Apr 14, 2005 11:37 pm Post subject:
----

Quote:

I have heard that finding generators for any random prime is a hard problem... is it true?

Yes, it's a hard problem because there is no formula to find a generator of a group. You must take a number test if it's a generator, yes we are happy else take another number and test again until you find one.

Author: data, Location: India

Posted: Sat Apr 16, 2005 9:01 pm Post subject:
----
hi,

There are precisely phi(p-1) generators in Fp. Finding one won't be so hard.

Data.

Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

output generated using printer-friendly topic mod, All times are GMT + 2 Hours

Page 1 of 1