Timeline for Conjecturally unsafe RSA primes $p=27a^2+27a+7$
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2017 at 3:20 | comment | added | Timothy Chow | @FelipeVoloch : One version of the Qi Cheng paper that joro found is titled, "A new class of unsafe primes." So I don't think joro can be accused of "clickbait." eprint.iacr.org/2002/109.pdf | |
| Oct 20, 2017 at 10:46 | answer | added | joro | timeline score: 7 | |
| Oct 19, 2017 at 15:53 | history | edited | Timothy Chow | CC BY-SA 3.0 |
added 1 character in body
|
| Oct 19, 2017 at 13:58 | comment | added | joro | @TomEllis Actually they are unsafe only for hardness of factorization not about discrete logs over finite fields. Will edit. Thanks. | |
| Oct 19, 2017 at 13:46 | comment | added | Tom Ellis | Can I suggest rewording "are unsafe for cryptographic reasons" to "are unsafe for cryptographic purposes"? I would be happy to make the edit myself but I'm not certain that you meant the latter so wanted to check. | |
| Oct 19, 2017 at 12:59 | comment | added | Davy Wybiral | @FelipeVoloch thanks for clearing up the probabilities. That's what I was looking for. | |
| Oct 19, 2017 at 10:12 | comment | added | joro | @FelipeVoloch I believe the popularity of this question is not from the "clickbait" but because it is linked from some popular site(s). | |
| Oct 19, 2017 at 8:24 | comment | added | joro | @FelipeVoloch feel free to edit. The title gives the quadratic form, so it is clear from the title the sequence is sparse. | |
| Oct 19, 2017 at 7:57 | comment | added | Felipe Voloch | @joro "Multiples of primes of the form blah are easily factorable" would have been an alternative. | |
| Oct 19, 2017 at 7:42 | comment | added | joro | @FelipeVoloch What title do you suggest? I thought this is standard term, even for sparse sequences as you note. | |
| Oct 19, 2017 at 7:40 | comment | added | Felipe Voloch | @joro Yes, it is interesting but doesn't deserve the "unsafe RSA" clickbait title. | |
| Oct 19, 2017 at 7:20 | comment | added | Felipe Voloch | @DavyWybiral The density of primes of size about $x$ is approximately $1/\log x$, while the density of primes of size $x$ in such a quadratic progression is at most $1/({\sqrt x}{\log x})$. If primes are chosen at random this essentially will never happen. You can try for yourself to see if you find these primes in the wild. People have done large scale searches for vulnerable (against other attacks) keys in use online factorable.net | |
| Oct 19, 2017 at 5:26 | comment | added | joro | @FelipeVoloch This is not threat to sound RSA implementation, but there is interest in mathematics and cryptography about factors which can be found efficiently. | |
| Oct 19, 2017 at 0:57 | comment | added | Davy Wybiral | @FelipeVoloch even if they are totally random I think the point is that some random primes might be less safe than others. But I wonder how many this would even represent. | |
| Oct 18, 2017 at 20:10 | comment | added | Felipe Voloch | It would be a terrible idea and it would raise suspicions of a deliberate trapdoor if the primes for RSA were chosen from a quadratic progression rather than randomly. | |
| Oct 18, 2017 at 19:03 | history | edited | GH from MO |
edited tags
|
|
| Oct 18, 2017 at 19:03 | comment | added | GH from MO | The conjecture mentioned in the post is true, see the proof under the link given in the post. | |
| S Oct 18, 2017 at 15:50 | history | suggested | J.J. Green | CC BY-SA 3.0 |
\mathrm for function name
|
| Oct 18, 2017 at 13:53 | review | Suggested edits | |||
| S Oct 18, 2017 at 15:50 | |||||
| Oct 18, 2017 at 13:02 | history | asked | joro | CC BY-SA 3.0 |