On Fri, Jul 31, 2015 at 02:36:03AM +, p...@securecottage.com wrote:
I have looked at your latest source to see if you have a possible common
factor for (p-1) and (q-1) in your RSA key generation code.
I've seen various proposals heres to generate what might be
stronger RSA keys. But 1
On Mon, 3 Aug 2015 at 14:09:33 + Viktor Dukhovni wrote:
On Mon, Aug 03, 2015 at 12:07:18AM -0600, Hilarie Orman wrote:
1. Use strong primes as in Rivest/Silverman. Simply described,
choose large primes r and s. Choose small factors i and j, gcd(i, j)
= 1. Find p such
Date: Mon, 3 Aug 2015 04:04:01 +
From: Viktor Dukhovni openssl-us...@dukhovni.org
On Sun, Aug 02, 2015 at 08:08:52PM -0600, Hilarie Orman wrote:
For primes p and q for which p-1 and q-1 have no common factor = n,
Other than 2 of course.
Of course.
probability of gcd(p, q) 1
On Sun, Aug 02, 2015 at 12:59:49AM +, p...@securecottage.com wrote:
I'd like to thank several people for looking into my assertion that it
is possible for common factors in p-1 and q-1 to leak from the
factorisation of n-1.
Hi Paul.
I came across a paper by Mckee and Pinch [1] you might
On Sun, Aug 02, 2015 at 08:08:52PM -0600, Hilarie Orman wrote:
For primes p and q for which p-1 and q-1 have no common factor = n,
probability of gcd(p, q) 1 is very roughly 1/n.
Hi
There's a typo or two here. Assuming p!=q, we always have gcd(p,q)=1.
Therefore, 1. Use strong primes as in
On Mon, Aug 03, 2015 at 12:07:18AM -0600, Hilarie Orman wrote:
1. Use strong primes as in Rivest/Silverman. Simply described,
choose large primes r and s. Choose small factors i and j, gcd(i, j)
= 1. Find p such that 1+2*i*r is prime and q such that 1+2*j*s is
prime.
On Sun, Aug 02, 2015 at 08:08:52PM -0600, Hilarie Orman wrote:
For primes p and q for which p-1 and q-1 have no common factor = n,
Other than 2 of course.
probability of gcd(p, q) 1 is very roughly 1/n.
That would be gcd(p-1, q-1), since gcd(p,q) is of course 1,
unless p == q.
Therefore,
This characteristic is not limited to common factors of p-1 and q-1. For
every factor of (p-1) (and similarly for q-1) there exists a k where p*q+k
having same factor. In this case p-1 and q+k are sharing the same factor:
p*q+k = (p-1)(q-1) + (p-1) + (q+k). Based on this GCD(n+x,n+y) for a range
.
Original Message
From: Viktor Dukhovni
Sent: Friday, July 31, 2015 22:07
To: openssl-dev@openssl.org
Reply To: openssl-dev@openssl.org
Subject: Re: [openssl-dev] common factors in (p-1) and (q-1)
On Fri, Jul 31, 2015 at 11:31:08PM +, p...@securecottage.com wrote:
I have checked through
For primes p and q for which p-1 and q-1 have no common factor = n,
probability of gcd(p, q) 1 is very roughly 1/n.
Therefore,
1. Use strong primes as in Rivest/Silverman. Simply described,
choose large primes r and s. Choose small factors i and j, gcd(i, j)
= 1. Find p such that 1+2*i*r is
On Fri, Jul 31, 2015 at 06:46:22PM +, Viktor Dukhovni wrote:
On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:
Cool observation. From running a bit of Python code, it looks like
the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at
least for random numbers
On Sat, Aug 01, 2015 at 01:50:00PM +, Ben Laurie wrote:
On Sat, 1 Aug 2015 at 14:22 mancha manc...@zoho.com wrote:
On Fri, Jul 31, 2015 at 06:46:22PM +, Viktor Dukhovni wrote:
On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:
Cool observation. From running a bit of
On Sat, 1 Aug 2015 at 14:22 mancha manc...@zoho.com wrote:
On Fri, Jul 31, 2015 at 06:46:22PM +, Viktor Dukhovni wrote:
On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:
Cool observation. From running a bit of Python code, it looks like
the probability that GCD(p-1, p-q)
On Fri, Jul 31, 2015 at 11:31:08PM +, p...@securecottage.com wrote:
Hi Mancha,
Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and
(q-1) will divide all 4 of the terms in the definition of p*q-1. Thus
it will be a common factor in the totient.
Hi Paul, many thanks for
On Sun, Aug 02, 2015 at 12:59:49AM +, p...@securecottage.com wrote:
He managed to get a common factor of
gcd(p-1,q-1) = 2 * 28559 from the following 1024 bit rsa generated key
(factorisation of p*q-1 is shown):
n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *
I'd like to thank several people for looking into my assertion that it
is possible for common factors in p-1 and q-1 to leak from the
factorisation of n-1.
Particularly, Viktor Dukhovni, for trying tens of thousands of key
generation iterations to see if common factors are possible.
-dev@openssl.org
Subject: Re: [openssl-dev] common factors in (p-1) and (q-1)
On Fri, Jul 31, 2015 at 4:43 PM, Blumenthal, Uri - 0553 - MITLL
u...@ll.mit.edu wrote:
I think adding the recommended check would be beneficial. Considering the
frequency of key generation, performance impact shouldn't
On Fri, Jul 31, 2015 at 4:43 PM, Blumenthal, Uri - 0553 - MITLL
u...@ll.mit.edu wrote:
I think adding the recommended check would be beneficial. Considering the
frequency of key generation, performance impact shouldn't matter all that
much.
Samuel's argument above is one I've heard before
On Fri, Jul 31, 2015 at 11:31:08PM +, p...@securecottage.com wrote:
I have checked through the key generation code of the openssl ssl code.
Not carefully enough...
I
hacked it to report the greatest common divisor of p-1 and q-1. I then ran
100 key generations. It only had greatest
On Fri, Jul 31, 2015 at 02:36:03AM +, p...@securecottage.com wrote:
Hi there,
I have looked at the RSA protocol a bit and have concluded that
1) common factors in (p-1) and (q-1) are also in the factorisation of
(p*q-1). 2) by factoring (p*q-1) you can come up with candidates for
On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:
Cool observation. From running a bit of Python code, it looks like the
probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at least for
random numbers between 2048 and 4096 bits long. It looks like putting in a
GCD(p-1,
Cool observation. From running a bit of Python code, it looks like the
probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at least for
random numbers between 2048 and 4096 bits long. It looks like putting in a
GCD(p-1, q-1) check will slow down finding suitable p and q by around a
On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:
Cool observation. From running a bit of Python code, it looks like
the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at
least for random numbers between 2048 and 4096 bits long. It looks
like putting in a GCD(p-1, q-1)
On Fri, Jul 31, 2015 at 12:35 PM, mancha manc...@zoho.com wrote:
If so, here's my quick dirty back-of-envelope calculation (mod bound)
for the probability the gcd of two randomly chosen integers x,y is at
most k:
k p(gcd(x,y)=k)
- --
1 60.79%
2 75.99%
On 31-07-2015 22:03, Viktor Dukhovni wrote:
Is finding sufficiently large factors a tractable problem?
p-1 will usually have a large prime factor. But for q-1 to have the same prime
factor is highly unlikely. The
probability that GCD(n1, n2) = d for random n1, n2 is 6/(d^2 pi^2). For
RSA-1024
Hi Mancha,
Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and
(q-1) will divide all 4 of the terms in the definition of p*q-1. Thus
it will be a common factor in the totient.
I have checked through the key generation code of the openssl ssl
code. I hacked it to report
: Friday, July 31, 2015 19:31
To: mancha
Reply To: openssl-dev@openssl.org
Cc: openssl-dev@openssl.org
Subject: Re: [openssl-dev] common factors in (p-1) and (q-1)
Hi Mancha,
Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and
(q-1) will divide all 4 of the terms in the definition of p
On Fri, Jul 31, 2015 at 01:42:01PM -0700, Bill Cox wrote:
You are correct, or at least very close. I was testing for GCD(p-1, q-1)
== 4, when I should have been testing for GCD(p-1, q-1) == 2, since p-1 and
q-1 are known to be even. Fixing that, I see that the probability of
having GCD(p-1,
Hi there,
I have looked at the RSA protocol a bit and have concluded that
1) common factors in (p-1) and (q-1) are also in the factorisation of (p*q-1).
2) by factoring (p*q-1) you can come up with candidates for squares in
the totient.
3) you can also come up with d mod commonfactor^2 if
29 matches
Mail list logo
