RSA_numbers_factored.py

[HermannSW]

Yes, I just looked today for those factored RSA numbers with quotient of primes bigger than 2 (6 in total).
They have at least one power of 2 between the prime numbers.

One factorization algorithm is Pollard's rho algorithm, with "x -> x**2 (mod n)":
https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm


For n=p*q with odd primes p, q we know that a**phi(n) = a**((p-1)*(q-1)) = 1 (mod n) for gcd(a,n)=1.
Just wrote this Python script to create graphviz graph for "x -> 2*x (mod n)"

Code: Select all

from sys import argv
from numpy import gcd
n = int(argv[1]) * int(argv[2])
print("digraph D {")
print("rankdir=LR")
for i in range(n):
    if gcd(i,n) > 1:
        print(i, "[style=filled]")
for i in range(n):
    print(i, "->", (2*i)%n)
print("}")

For n=7*17, 2**(int(log2(n))//2)=8 is between 7 and 17 in this graph:
GraphvizFiddle share link
Part:

7_13.part.png

7_13.part.png (74.47 KiB) Viewed 4910 times

Not clear whether knowing such power of two can help on factoring n …

[HermannSW]

There is a new MicroPython version of "RSA number⁠s factored".
It has been tested on Raspberry RP2040 MCU.

Why do multiple 100-digit arbitrary precision arithmetic on an MCU?
Because we can

Validation demo takes 3:09min on RP2040 MicroPython, instead of 1 second in Python or browser JavaScript version though ...
https://github.com/orgs/micropython/discussions/10869

RSA_numbers_factored_mp.py.png

RSA_numbers_factored_mp.py.png (90.97 KiB) Viewed 4831 times

P.S:
I used

Code: Select all

l,n,p,q = RSA.get(59)[slice(4)]

in Python sofar, but "slice" is not available in MicroPython, so I used this instead:

Code: Select all

l,n,p,q = RSA.get(59)[0:4]

As in transpiled JavaScript version I had to implement lcm(), gcd(), isprime() for MicroPython, because sympy is unavailablle.

[HermannSW]

RSA-numbers as product of two primes have exactly two representations as sum of squares [if both primes are "≡1 (mod 4)", provided by new RAS().factored_1_1()]:

Code: Select all

$ python -q
>>> from RSA_numbers_factored import RSA, square_sums, has_factors_1_1
>>> R = RSA()
>>> square_sums(R.square_sum_prod(R.get(59)))
[[38768728061109707828243001823, 264836754409721537369435955610], [93861205413769670113229603198, 250662312444502854557140314865]]
>>> 

I just learned how to determine odd semiprime prime factors, if knowing both representations as sum of squares:
viewtopic.php?p=2088400#p2088400

There I did it for 3-digit prime factors, but method works efficiently for big RSA numbers (here RSA-129) as well.
2nd last identity shows that sum of squares for (a, b) and (c, d) is n.
Last identitiy shows that interpreting (a,b) and (c,d) as Gaussian integers, Gaussian "gcd" ggcd() can determine both prime factors of n easily (in less than 1 second):

Code: Select all

$ python -q
>>> from RSA_numbers_factored import square_sum_prod,square_sums, rsa, digits,ggcd
>>> def sos(t):
...     return t[0]**2 + t[1]**2
... 
>>>

Code: Select all

>>> l,n,p,q = rsa[5][0:4]
>>> digits(n)
129
>>> (a,b),(c,d) = square_sums(square_sum_prod([0,0,p,q]))
>>> sos( (a,b) ) == sos( (c,d) ) == n == p * q
True
>>> { p, q } == { sos(ggcd( (a,b), (c,d) )), sos(ggcd( (a,b), (c,-d) )) }
True
>>> 

[HermannSW]

If odd semiprime n=p*q with p=a²+b² and q=c²+d², then

Code: Select all

n == (a*c-b*d)² + (b*c+a*d)² == (a*c+b*d)² + (b*c-a*d)²

by Brahmagupta–Fibonacci identity.

Furthermore, by multiplying (a*c+b*d) with (b*c-a*d+):

Code: Select all

n == (a*c)²+(b*d)²+(a*d)²+(b*c)²

New RSA class function .square_sums_4() determines the 4 square numbers:
https://github.com/Hermann-SW/RSA_numbe ... are_sums_4

Small usage example:

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ python -q
>>> from RSA_numbers_factored import RSA
>>> RSA=RSA()
>>> RSA.square_sums_4(59)
(179348979911745603741332779404, 85487774497975933628103176206, 105946792191696573364448656521, 144715520252806281192691658344)
>>> sum([x**2 for x in RSA.square_sums_4(59)]) == RSA.get(59)[1]
True
>>> 

[HermannSW]

Some postings ago I reported about how to use modified RSA_numbers_factored.py in MicroPython on micro controller (just for fun).

Today during long hike with dog in forest I wanted to compute some RSA number related formula.
I used small values of primes p and q and the unique sum of squares for them.
In the end I had to use normal smartphone calculator to compute remainders of division.
So I asked myself whether I can run Python on Android.

Simple answer is yes, and there are alternatives.
I decided to go with non-free Pydroid3 (3 days free test, then 2$/month or 16$/lifetime).
After installing I was able to compute "2**65537 % 65537" in the forest thanks to Python.

At home I told my older son, and he did not search in playstore but in search engine.
He came up with open source QPython, but that asked to install from playstore, and playstore said that it cannot install on my Android 11.

So I will go with Pydroid3. Initially I selected weekly charge for 3 days free testing.
It turned out not to be possible to change that to lifetime during free 3-day trial.
I canceled subscription and will buy lifetime after free trial ends on Monday.

The first small scripts were easy to type in and run.
Installation of sympy was easy as well with builtin Pip (see left below).
Running mathplotlib example automatically installed mathplotlib and produced nice 3D function on display.

So I wanted to copy RSA_numbers_factored.py onto smartphone, but did not find the right directory.
This posting revealed the lib directory:
https://stackoverflow.com/a/70714408/5674289
On my Android it was Python 3.9:

Code: Select all

/data/user/0/ru.iiec.pydroid3/files/aarch64-linux-android/lib/python3.9

So I uploaded RSA_numbers_factored.py with AndFTP onto smartphone Download directory.
Then opened with Pydroid3, and stored with "save as" in Pydroid3 internal filesystem under above directory.

Next I created small Pydroid3_demo.py:
https://github.com/Hermann-SW/RSA_numbe ... d3_demo.py
That was necessary since test __name__ == "__main__" does not work in Pydroid3.
And uploaded it into Internal storage/Documents/Pydroid3 directory.
Finally I opened in Pydroid3 (see middle) and clicked run button at bottom.
The output of demo can be seen right:

Pydroid3_demo.jpg

Pydroid3_demo.jpg (101.49 KiB) Viewed 4645 times

So cool to be able to run Python, with sympy, mathplotlib, arbitrary precision arithmetic, ... anywhere even offline without connectivity.

I added new section "Non-standard Python environments" to github repo (with MicroPython and Android subsections):
https://github.com/Hermann-SW/RSA_numbe ... vironments

[HermannSW]

I installed Pydroid3 on very old (2015) Lenovo Tab A10 10.1" Android tablet, and pip installed sympy and RSA_numbers_factored.py as described.
The Qualcomm® MSM8909 32-bit 1.3 GHz Quad-Core is much slower than today's smartphones, and so execution can be seen to proceed several seconds.
Anyway still much faster than 3:09min on microcontroller — and 10.1" display is definitely preferable to my Galaxy A40 5.9" display:

[HermannSW]

Until now source of semi primes were RSA numbers only.
I just got new cert for my personal website and wanted to know more.

I use this openssl version:

Code: Select all

pi@pi400-64:~ $ openssl version
OpenSSL 1.1.1n  15 Mar 2022
pi@pi400-64:~ $ 

I learned that this command creates a new cert with private key, typically with 4096 bits, here minimal value of 512 bits allowed by openssl:

Code: Select all

pi@pi400-64:~ $ openssl req -x509 -newkey rsa:512 -keyout key.pem -out cert.pem -days 365
Generating a RSA private key
....+++++++++++++++++++++++++++
.....................+++++++++++++++++++++++++++
writing new private key to 'key.pem'
Enter PEM pass phrase:
Verifying - Enter PEM pass phrase:
-----
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:
State or Province Name (full name) [Some-State]:
Locality Name (eg, city) []:
Organization Name (eg, company) [Internet Widgits Pty Ltd]:
Organizational Unit Name (eg, section) []:
Common Name (e.g. server FQDN or YOUR name) []:
Email Address []:
pi@pi400-64:~ $ 

Passphrase is required, for all other inputs just pressing RETURN is ok.

This command creates visible output of private key:

Code: Select all

pi@pi400-64:~ $ openssl rsa -noout -text -in key.pem
Enter pass phrase for key.pem:
RSA Private-Key: (512 bit, 2 primes)
modulus:
    00:bb:30:3c:13:c5:70:b5:0e:67:32:f5:d3:79:f0:
    d3:54:31:49:31:49:c2:6e:2c:1b:f7:fb:7e:58:c8:
    43:4c:5f:e4:ac:39:a3:78:b9:be:79:a1:c1:f6:03:
    86:01:da:d7:a0:6e:3c:5d:ff:34:7c:dc:18:b2:0b:
    f6:48:db:21:43
publicExponent: 65537 (0x10001)
privateExponent:
    38:63:f4:85:44:42:8a:d8:b6:f0:1c:2c:44:1c:ef:
    9c:fa:68:01:48:26:21:88:7a:38:7f:73:f5:8d:06:
    f1:17:a2:21:2a:fa:dd:79:3b:5c:33:9c:47:c6:68:
    d2:7c:fd:d4:7a:8b:6c:65:14:0d:33:85:45:e0:ad:
    94:8d:e7:49
prime1:
    00:e9:92:74:b3:4b:6e:ab:1e:d3:2b:4a:06:02:10:
    ed:42:fa:28:4e:ee:43:a0:ed:77:45:d6:b9:48:92:
    b3:e1:55
prime2:
    00:cd:29:99:a1:16:6e:8d:ef:7e:e0:61:cf:f1:64:
    c9:87:82:1a:b9:56:5d:0e:92:22:a6:1a:8f:d2:bd:
    be:d8:37
exponent1:
    2b:17:8d:16:43:15:70:d6:a8:08:f5:88:34:3b:61:
    3a:99:22:74:a5:7a:ae:a7:00:f9:4e:8b:32:7b:76:
    5a:5d
exponent2:
    07:34:d4:de:a1:a9:14:77:3b:1f:aa:8f:e1:4c:c6:
    ff:69:84:82:ca:13:ce:b5:37:5e:5a:44:7f:04:87:
    35:95
coefficient:
    00:c6:74:da:f8:27:8f:f9:0f:9f:5c:fa:77:65:4f:
    47:72:b4:4d:1b:64:65:a9:44:06:30:a2:8a:f1:a9:
    4f:27:b5
pi@pi400-64:~ $ 

I wrote short script for extracting modulus, prime1 and prime2 from private key:

Code: Select all

#!/bin/bash
openssl rsa -noout -text -in $1 > /tmp/key.dec
echo -n "p=0x"
for f in `cat /tmp/key.dec | \
sed -n "/prime1:/,/prime2:/p" | tail -n+2 | head -n-1 | \
sed "s/ //g;s/:/ /g" `; do echo -n $f; done
echo
echo -n "q=0x"
for f in `cat /tmp/key.dec | \
sed -n "/prime2:/,/exponent1:/p" | tail -n+2 | head -n-1 | \
sed "s/ //g;s/:/ /g" `; do echo -n $f; done
echo
echo -n "n=0x"
for f in `cat /tmp/key.dec | \
sed -n "/modulus:/,/publicExponent:/p" | tail -n+2 | head -n-1 | \
sed "s/ //g;s/:/ /g" `; do echo -n $f; done
echo
rm /tmp/key.dec

Output:

Code: Select all

pi@pi400-64:~ $ ./dec key.pem 
Enter pass phrase for key.pem:
p=0x00e99274b34b6eab1ed32b4a060210ed42fa284eee43a0ed7745d6b94892b3e155
q=0x00cd2999a1166e8def7ee061cff164c987821ab9565d0e9222a61a8fd2bdbed837
n=0x00bb303c13c570b50e6732f5d379f0d35431493149c26e2c1bf7fb7e58c8434c5fe4ac39a378b9be79a1c1f6038601dad7a06e3c5dff347cdc18b20bf648db2143
pi@pi400-64:~ $ 

Verification in Python:

Code: Select all

pi@pi400-64:~ $ python
Python 3.9.2 (default, Feb 28 2021, 17:03:44) 
[GCC 10.2.1 20210110] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> p=0x00e99274b34b6eab1ed32b4a060210ed42fa284eee43a0ed7745d6b94892b3e155
>>> q=0x00cd2999a1166e8def7ee061cff164c987821ab9565d0e9222a61a8fd2bdbed837
>>> n=0x00bb303c13c570b50e6732f5d379f0d35431493149c26e2c1bf7fb7e58c8434c5fe4ac39a378b9be79a1c1f6038601dad7a06e3c5dff347cdc18b20bf648db2143
>>> n == p * q
True
>>> 

For less than 512-bit semi primes with openssl I might build myself, and reduce the 512-bit minimal modulus length.
Not for using that cert (that would be insecure), but to create factoring input primes as openssl does with low modulus for prime factoring testing.


P.S:
The two primes are of nearly the same size:

Code: Select all

>>> p/q
1.1384736133466302
>>> 

P.P.S:
155-diigit number RSA-155 has length 512-bits:

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ python -q
>>> from RSA_numbers_factored import RSA, bits
>>> RSA=RSA()
>>> print(bits(RSA.get(155)[1]))
512
>>> 

[HermannSW]

Just found tweet on RSA key generation implementation vulnerability (not RSA itself):
https://twitter.com/hanno/status/1503380866990592014

A common strategy for cryptographic research is to take an old attack and see if you find vulnerable implementations. I took this to a new level with a 379 year old attack: Breaking RSA keys with Fermat's factorization algorithm

Many printers were affected, the vulnerability got CVE-2022-26320 assigned.

The interesting part on How "close" do primes need to be in order to be vulnerable?:
https://fermatattack.secvuln.info/

fermat.png

fermat.png (56.91 KiB) Viewed 4420 times

I must be missing something, but for all 25 already factored RSA numbers the difference between both primes is 2**414 at most, so all should be easy to factorize?!?!?

max_diff.jpg

max_diff.jpg (76.72 KiB) Viewed 4420 times

Seems I will have to implement fermat attack and have a look ...

[HermannSW]

I found @hannob's implementation of fermat.py:
https://github.com/badkeys/badkeys/blob ... /fermat.py

It uses gmpy2, so these steps are needed to run his code:

Code: Select all

sudo apt-get install libgmp3-dev libmpfr-dev libmpc-dev
pip install gmpy2

Simple test just worked:

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ python -q
>>> from fermat import *
>>> fermat(509*1003)
{'p': 1003, 'q': 509, 'a': 756, 'b': 247, 'debug': 'Fermat factorization after 42 rounds, b=247'}
>>> 

But testing for smallest RSA number RSA-59 was quick but unsuccessful:

Code: Select all

>>> from RSA_numbers_factored import rsa
>>> l,n,p,q = rsa[0][0:4]
>>> fermat(n)
False
>>> fermat(n)
False
>>> 

So definitely not the magic semiprime factoring algorithm for prime differences up to 2**517.

[HermannSW]

During vacation I have enough time, I completed documentation ...
https://github.com/Hermann-SW/RSA_numbe ... ored.py.md

... and v1.10 — it took a long time:
https://github.com/Hermann-SW/RSA_numbe ... actored.py

Code: Select all

v1.10

add uniq arg to RSA().square_sums()
add smp1m4 list of primes =1 (mod 4) less than 1000
add sqtst()
add lazydocs doc with Makefile fixing Example[s] bugs, docstrings up to and including SECTION03
add sq2d()
add MicroPython version
add square_sums_4()
avoid redundant return type in "Returns:", now lazydocs Makefile handles that
completed documentation, fix small typos, correct some hinting types, new examples

Code: Select all

Todo: show lazydocs class member functions as "method" and not as "function"
New makefile doc|pylint|validate targets
"make pylint" clean (top line disable and pylint options)
make sure every function/method gets called at least once in validation
pylint warning related simplifications
"validate" target to compare with "validate.good", new "black" target
code formatting now with "black", results in need for --max-module-lines=2500
new "doc_diff" target
blacked Pydroid3 demo, then made pylint clean
updated both README.md, added table of contents

Making RSA_numbers_factored.py pylint clean took a big amount of work.
Even after that work, I will not handle eg. invalid-name warning.
And some warnings cannot be fixed at all:
pylint default maximal line length is 100, so any more than 100 digit numbers (eg. RSA-110) result in warnings.

I had to disable some warnings in source code ...

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ head -2 RSA_numbers_factored.py 
# pylint: disable=R0201, C0103
#                 no-self-use, invalid-name
pi@pi400-64:~/RSA_numbers_factored/python $ 

... and some via command line options ("\d{30}" regexp disables long-lines warnings for lines with 30-digit or longer numbers):

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ sed -n "/^pylint:/,/^$/p" Makefile 
pylint: RSA_numbers_factored.py
	pylint --ignore-long-lines="\d{30}" --max-module-lines=2500 $<

pi@pi400-64:~/RSA_numbers_factored/python $ 

"--max-module-lines=2500" was needed after I decided to use Python formatter black, that kicked number of lines above 1600.

The Makefile got some new targets:
https://github.com/Hermann-SW/RSA_numbe ... n#makefile

Makefile.png

Makefile.png (54.77 KiB) Viewed 4341 times

P.S:
I was a bit skeptical when running "black" Python formatter first, but the big number of changes in the diff made sense:
https://github.com/Hermann-SW/RSA_numbe ... e04978ce39

Because I made sure before, that each and every function and RSA class method is executed at least once in "validate" Makefile target, from now on "make black" with automatically executed "make validate" will be run before any change commit for RSA_numbers_factored.py

black_first_executed.png

black_first_executed.png (78.24 KiB) Viewed 4309 times

P.P.S:
The lines grew from 1000 to >1600 because black enforces 1 line per array entry:

black_diff_tw.png

black_diff_tw.png (90.81 KiB) Viewed 4302 times

[HermannSW]

OpenSSL key genereration as well as connecting to a server over ssh the first time show random art:

OpenSSL.random_art.png

OpenSSL.random_art.png (34.56 KiB) Viewed 4203 times

Here is a paper that deals with the question, whether the random art does not reveal information allowing to factor the semiprime:
http://www.dirk-loss.de/sshvis/drunken_bishop.pdf


I wanted to create graphical representation for already factored RSA numbers, and since they were factored already, revealing prime factor p (1-bits = shown rows) and prime factor q (1-bits = shown columns) for an RSA number is no problem. The image is the "and" function on the row and column bits. Highest bit for both is always set, so top left corner always has blue dot. RSA number prime factors are always odd, so bottom right dot is blue always as well.

For new demo RSA_svg.py I used "black" Python formatted as well, and made it pylint clean (the black message shortcake color emoji became visible after I selected "Noto Mono Regular" in lxterminal Preferences, apt installed "fonts-noto-color-emoji" package and rebooted, because "fc-cache" execution had no effect):

RSA_svg.py.png

RSA_svg.py.png (40.23 KiB) Viewed 4203 times

Even on Pi400 it takes half a minute to create the huge SVG file, I converted it to only 829 byte .png for forum attachment:

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ python RSA_svg.py 250 > 250.svg
pi@pi400-64:~/RSA_numbers_factored/python $ time convert 250.svg 250.svg.png 

real	0m31.664s
user	0m28.254s
sys	0m3.251s
pi@pi400-64:~/RSA_numbers_factored/python $ file 250.svg.png 
250.svg.png: PNG image data, 414 x 415, 2-bit colormap, non-interlaced
pi@pi400-64:~/RSA_numbers_factored/python $ 

I really like what black code formatter did with what I typed in:
https://github.com/Hermann-SW/RSA_numbe ... RSA_svg.py


And here is biggest factored sofar RSA-250 as SVG:
(.svg can be viewed with "eog" and "gimp", as well as "chromium-browser" and "firefox")

250.svg.eog.png.png

250.svg.eog.png.png (112.64 KiB) Viewed 4203 times

[HermannSW]

I dd investigation "Multiple precision integer performance across languages":
https://github.com/Hermann-SW/RSA_numbe ... -languages

Part of that was benchmark to determine sum of squares for 2467-digit prime number.

I added comment in open sympy issue that gcd() on Gaussian integers is broken:
https://github.com/sympy/sympy/issues/1 ... 1550977489

Immediately after that the issue got closed, because it was fixed in 2020 already.

I created Python script to determine sum of squares using sympy gcd, and that showed 40% runtime increase for 2467-digit prime over 2010 Robin Chapman code I used sofar for "sq2()":
https://github.com/sympy/sympy/issues/1 ... 1551635777

Later I used that script for a 10,000-digit prime from "Prime Curious!" website:
https://t5k.org/curios/index.php?start=4001

Finally I used 36401-digit prime:
https://t5k.org/curios/page.php?number_id=3658

Sum of squares computation took 2011 seconds, but final gcd() took only 13 seconds, majority time for determination of sqrt(-1) (mod p):

Code: Select all

pi@pi400-64:~ $ head -8 36401.py 
"""
sq2_sympy.py from here (plus time print() in "sq2()"):
https://github.com/sympy/sympy/issues/15358#issuecomment-1551635777

2.5GHz i7-11850H
1998.6601960659027s  a = sqrt(-1) (mod p)
2011.4160270690918s  x, y = gcd(p, a + I).as_real_imag()
"""
pi@pi400-64:~ $ 

Verification is done instantaneously:

Code: Select all

pi@pi400-64:~ $ time python 36401.py 
36401
True

real	0m0.179s
user	0m0.153s
sys	0m0.026s
pi@pi400-64:~ $ 

https://gist.github.com/Hermann-SW/c717 ... 3473f59e29

36401.py.jpg

36401.py.jpg (103.35 KiB) Viewed 3917 times

So why did I go for 2,467-, then 10,000- and then 36,401-digit primes?
Largest twin primes known as of today are 2996863034895 × 2¹²⁹⁰⁰⁰⁰ ± 1, with 388,342 decimal digits:
https://en.wikipedia.org/wiki/Twin_prim ... win_primes


sympy gcd runtime will be fine to determine sum of squares for "p = 2996863034895 × 2¹²⁹⁰⁰⁰⁰ + 1".
But determination of "sqrt(-1) (mod p)" needs speedup to get the 11× bigger number processed in reasonable time.


P.S:
The 36401-digit prime is the largest known palindromic prime:

palin.py.jpg

palin.py.jpg (50.17 KiB) Viewed 3892 times

[HermannSW]

I continued the "gaussian integer gcd()" performance evaluation.
To numbers so big (388432 decimal digits, or 1.29 million bits) that the RSA-numbers up to 617 decimal digits or 2048 bits are "small".
Details here:
https://github.com/Hermann-SW/RSA_numbe ... -benchmark

I did precompute "sqrtm1 = sqrt(-1) (mod p)" in order to only measure runtime for computing "gcd(p, sqrtm1 + I)".
Runtimes for computing that gaussian integer gcd() are quadratic in the input size (up to 42 minutes(!) for 388342-digit prime), so gaussian intgeger gcd() is an efficient algorithm.

I used simple quadratic regression solver with matplotlib ...
viewtopic.php?t=351919
... and this is the final diagram:

sympy_gaussian_integer_gcd_benchmark.png

sympy_gaussian_integer_gcd_benchmark.png (45.42 KiB) Viewed 3541 times

P.S:
Found list of largest known primes:
https://t5k.org/primes/lists/all.txt
The biggest number I used is only rank 5038 on that list, but big enough for seeing the "quadratic in input size" runtime:

Code: Select all

 rank  description                     digits   who   year comment
-----  ------------------------------- -------- ----- ---- --------------
 5038  2996863034895*2^1290000+1         388342 L2035 2016 Twin (p+2)
...
 5058  2145*2^1099064+1                  330855 L1792 2013 Divides Fermat F(1099061)
....
 5068  1705*2^906110+1                   272770 L3174 2012 Divides Fermat F(906108)
 ...
 5077  3756801695685*2^666669+1          200700 L1921 2011 Twin (p+2)
...
 5092  65516468355*2^333333+1            100355 L923  2009 Twin (p+2)

[HermannSW]

I bought new fast AMD Ryzen 5 7600X CPU PC, and did run sqrtm1 with it. As described, I have seen sequential (single thread) speedups between 25.5% and 33.2% compared to i7-11850H CPU, nice:
viewtopic.php?p=2117515#p2117515

I did factor RSA numbers with parallel number field sieve cado-nfs.py, that shows more than 10× total time than elapsed time (7600X in 6C/12T mode). Last night I did factor 140 decimal digit of 466-bit number RSA-140 in 11:04:51h, and updated the double logarithmic regression curve:
https://github.com/Hermann-SW/RSA_numbe ... d#cado-nfs

cado-nfs.RSA-110..140.tw.png

cado-nfs.RSA-110..140.tw.png (62.73 KiB) Viewed 2169 times

After factoring RSA-x with x<130 became so quick, I factored p-1 and q-1 for RSA-x=p*q with 220 <= x <= 250:
https://github.com/Hermann-SW/RSA_numbe ... -1-and-q-1

With commit 27df24d I updated the determined factorizations as factorization dictionaries to RSA_numbers_factored.(py|js|gp).

I have not ported everything to PARI/GP RSA_numbers_factored.gp yet (a lot Python stuff is commented out), but implemented today "dict_int()"
https://github.com/Hermann-SW/RSA_numbe ... #L522-L533
so that I was able to verify the added (and already existing) factorization dicitionaries:

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/pari $ gp -q
? \r RSA_numbers_factored
validate(rsa): ✓
? 

The validation output of Python and JavaScript/NodeJS versions changed, since now 0 RSA numbers are factored without factorization dictionaries:

RSA_numbers_factored.vallidation_demo.png

RSA_numbers_factored.vallidation_demo.png (45.12 KiB) Viewed 2169 times

[HermannSW]

...
I learned that this command creates a new cert with private key, typically with 4096 bits, here minimal value of 512 bits allowed by openssl:
...
Passphrase is required, for all other inputs just pressing RETURN is ok.

Oprion "-nodes" gets rid of the need to provide a passphrase.

This command creates visible output of private key:
...

I wrote short script for extracting modulus, prime1 and prime2 from private key:
...

Output:
...

Verification in Python:
...

This is new "gen" bash script ("</dev/zero" fills all dialog fields):

Code: Select all

#!/bin/bash
openssl req -x509 -newkey rsa:512 -keyout key.pem -nodes </dev/zero 2>/dev/null

And this new "dec" script:

Code: Select all

#!/bin/bash
openssl rsa -noout -text -in key.pem > /tmp/key.dec
echo -n "p=0x"
for f in `cat /tmp/key.dec | \
sed -n "/prime1:/,/prime2:/p" | tail -n+2 | head -n-1 | \
sed "s/ //g;s/:/ /g" `; do echo -n $f; done
echo ";"
echo -n "q=0x"
for f in `cat /tmp/key.dec | \
sed -n "/prime2:/,/exponent1:/p" | tail -n+2 | head -n-1 | \
sed "s/ //g;s/:/ /g" `; do echo -n $f; done
echo ";"
echo -n "n=0x"
for f in `cat /tmp/key.dec | \
sed -n "/modulus:/,/publicExponent:/p" | tail -n+2 | head -n-1 | \
sed "s/ //g;s/:/ /g" `; do echo -n $f; done
echo ";"
rm /tmp/key.dec
echo -e "print(n==p*q)\nprint(p*1.0/q)"

Usage:

Code: Select all

pi@raspberrypi4B2:~/ssl $ ls
pi@raspberrypi4B2:~/ssl $ gen
pi@raspberrypi4B2:~/ssl $ ls
key.pem
pi@raspberrypi4B2:~/ssl $ dec
p=0x00e17ddd91fc9ee7da56c5162176d4878a4b671f5a363b97b8da6cab2f20b43185;
q=0x00c49cf16f621c94a1277df664172c01898c44f5703478b2ed01cbe41256eb0ff1;
n=0x00ad2e9b0063f476f76a5d2da27dfeabc083e8aafdc2f66678e5313766bda796c55be78370e68726697943eef657290c0d449eaa3ac940a4bb89d167ae7ba06935;
print(n==p*q)
print(p*1.0/q)
pi@raspberrypi4B2:~/ssl $ 

Why appending semicolons to first 3 lines?
Not because of Python (they don't hurt), but to avoid output for PARI/GP.

Now Python and PARI/GP can verify:

Code: Select all

pi@raspberrypi4B2:~/ssl $ gen; dec | python
True
1.0967038055612182
pi@raspberrypi4B2:~/ssl $ dec | gp -q
1
1.0967038055612182041316241556390419379
pi@raspberrypi4B2:~/ssl $ gen; dec | python
True
1.1242649697263756
pi@raspberrypi4B2:~/ssl $ 

P.P.S:
155-diigit number RSA-155 has length 512-bits:

Code: Select all

pi@pi400-64:~/RSA_numbers_factored/python $ python -q
>>> from RSA_numbers_factored import RSA, bits
>>> RSA=RSA()
>>> print(bits(RSA.get(155)[1]))
512
>>> 

I did factor slightly less than 512bit RSA-number RSA-150 in 38:26:37h on 24C/48T Intel Xeon E5 6126.

For less than 512-bit semi primes with openssl I might build myself, and reduce the 512-bit minimal modulus length.
Not for using that cert (that would be insecure), but to create factoring input primes as openssl does with low modulus for prime factoring testing.

Needed if not wanting to wait for 38h for each cado-nfs multithreaded factoring ...


Another way of reducing factoring time is to use multiple computers with cado-nfs:
https://sympa.inria.fr/sympa/arc/cado-n ... 00004.html

I used 3 computers:

gandalf 24C/48T, factors RSA_120 in 0:48:18 alone
elrond 24C/48T, factors RSA-120 in 0:45:58 alone
7600x 6C/12T, factors RSA-120 in 0:57:19 alone
...
...
That was successful, I captured smartphone video of the 4 windows in action.
Factoring RSA-120 completed in 0:25:06, distributed phase ended after 17:30min.

So best single computer multithreaded factoring runtime 0:45:58 gets reduced to 54.6% runtime (0:25:06h).