Prev: what is probability to create two equal hashes for md5 algorithm
Next: help needed
From: Peter Fairbrother on 3 Feb 2007 17:27
What's the best way to construct a large prime (plus a generator) so that it
is easy to find discreet logs?

If you were trying to backdoor a DLP-based system by choosing the wrong
prime, how would you go about choosing it?


Thanks,


--
Peter Fairbrother

From: Scott Contini on 3 Feb 2007 20:45
On Feb 4, 9:27 am, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:
> What's the best way to construct a large prime (plus a generator) so that it
> is easy to find discreet logs?
>
> If you were trying to backdoor a DLP-based system by choosing the wrong
> prime, how would you go about choosing it?
>
> Thanks,
>
> --
> Peter Fairbrother

One solution is to make p-1 smooth.
In other words, find a set of small primes q_1, ... , q_k such that
p = 2 * q_1 ^ e_1 * ... * q_k ^ e_k + 1
is prime. Then you can compute discrete logs modulo p by
http://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm

Scott


From: Amit on 3 Feb 2007 21:13
On Feb 4, 12:45 pm, "Scott Contini" <the_great_cont...(a)yahoo.com>
wrote:
> On Feb 4, 9:27 am, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:
>
> > What's the best way to construct a large prime (plus a generator) so that it
> > is easy to find discreet logs?
>
> > If you were trying to backdoor a DLP-based system by choosing the wrong
> > prime, how would you go about choosing it?
>

Would someone who is using your "wrong" prime know there is a
trapdoor ? Or you want to keep even this information secret?

>
> One solution is to make p-1 smooth.
> In other words, find a set of small primes q_1, ... , q_k such that
> p = 2 * q_1 ^ e_1 * ... * q_k ^ e_k + 1
> is prime. Then you can compute discrete logs modulo p byhttp://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm
>
> Scott

If someone else finds out that p-1 is k-smooth, then he/she can also
compute discrete logs.

From: Amit on 3 Feb 2007 21:17
On Feb 4, 1:13 pm, "Amit" <amitabh...(a)gmail.com> wrote:
>
> If someone else finds out that p-1 is k-smooth, then he/she can also
> compute discrete logs.

to avoid confusion with the re-use of letter k, let p-1 be b-smooth.

From: Peter Fairbrother on 3 Feb 2007 22:47
Amit wrote:

>> On Feb 4, 9:27 am, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:
>>
>>> What's the best way to construct a large prime (plus a generator) so that it
>>> is easy to find discreet logs?
>>
>>> If you were trying to backdoor a DLP-based system by choosing the wrong
>>> prime, how would you go about choosing it?
>>
>
> Would someone who is using your "wrong" prime know there is a
> trapdoor ? Or you want to keep even this information secret?

It's desireable, but not essential.

Pohlig-Hellman I know of - any other ideas?




--
Peter Fairbrother

 |  Next  |  Last
Pages: 1 2 3
Prev: what is probability to create two equal hashes for md5 algorithm
Next: help needed