Brimstone for cracking RSA. (jk)

SarK0Y · 2020-08-09, 20:11

Story of tails, windows and how it impacts integer factorization..
In other words, MILESTONE has been done :D

From the very start of my journey to discover the innards of stubborn IF, the prime goal was to have
developed binary-search-tree algos. At some point, it seemed utterly impossible. But here we go..

Actually, algo consists of three stages..

it picks initial (probable) Z’s (pZ_L and pZ_R) up (Z = P + Q, N = P*Q). So, now algo needs to guess which one is closest to original Z.

for pZ_L, it generates N_L which is closest to N from left/right and the same way for N_R of pZ_R.

for N_R/L, it collects statistics of bit windows against N (their positions, widths..)..

Window(N, EntryPoint, Width) == NOT Window(N_L, EntryPoint, Width).

For instance, let Window(N, EntryPoint, Width) == “010”, then Window(N_L, EntryPoint, Width) == “101”. And now it’s possible to choose probable Z according collected statistics for given iteration.

For tests, RSA-150 (https://en.wikipedia.org/wiki/RSA_numbers#RSA-150) has been taken, criterion to go left/right is widths of greatest windows. Output…

test mode gets activated
Wrong turn @ 1
Wrong turn @ 2
Wrong turn @ 3
Wrong turn @ 4
Wrong turn @ 5
Wrong turn @ 6
Wrong turn @ 7
Wrong turn @ 8
Wrong turn @ 9
Wrong turn @ 10
Wrong turn @ 11
Wrong turn @ 12
Wrong turn @ 13
Wrong turn @ 14
Wrong turn @ 15
Wrong turn @ 16
Wrong turn @ 17
Wrong turn @ 18
Wrong turn @ 19
Wrong turn @ 20
Wrong turn @ 21
Wrong turn @ 22
Wrong turn @ 23
Wrong turn @ 24
Wrong turn @ 25
Wrong turn @ 26
Wrong turn @ 27
Wrong turn @ 28
Wrong turn @ 29
Wrong turn @ 30
Wrong turn @ 31
Wrong turn @ 32
Wrong turn @ 33
Wrong turn @ 34
Wrong turn @ 35
Wrong turn @ 36
Wrong turn @ 37
Wrong turn @ 38
Wrong turn @ 39
Wrong turn @ 40
Wrong turns == 40
nice turns == 208
Total iterations == 248

In short, algo doesn’t do gaps (good and bad turns ain’t shuffled/mixed) even with such rather primitive criterion.
Archive: https:// sourceforge . net /projects/fastprimecruncher/Mod note URL intentionally broken. Sourceforge reports it as malware.
Password for archive: ᬓꨒꛏ78🁶

CRGreathouse · 2020-08-10, 04:21

Fantastic! Unfortunately, Aoki, Kida, Shimoyama, & Ueda already factored RSA-150, so it's not a good way to show that your method works. Could you demonstrate it with this smaller number, please?

3817396723515136582858035291731476702231874047478035390874743899933916107585885458479075057627686466112442032963859000272684225286856787555319737

I promise that it was (pseudo-)randomly generated* and that I've kept the factorization a secret (even from myself). This number isn't considered hard to factor, and so it won't of itself demonstrate a breakthrough, but it would make a better example. (Of course if you could factor such examples quickly enough it would suggest either collusion or a breakthrough, either in factorization or RNG cracking.)

* Brent's XORGEN.

SarK0Y · 2020-08-10, 10:32

Quote:

Originally Posted by CRGreathouse

Fantastic! Unfortunately, Aoki, Kida, Shimoyama, & Ueda already factored RSA-150, so it's not a good way to show that your method works. Could you demonstrate it with this smaller number, please?

3817396723515136582858035291731476702231874047478035390874743899933916107585885458479075057627686466112442032963859000272684225286856787555319737

for now, it's just a test mode, so it takes original P & Q

Dr Sardonicus · 2020-08-10, 12:23

MODERATOR NOTE: Thread moved to Miscellaneous Math

Quote:

Originally Posted by SarK0Y

for now, it's just a test mode, so it takes original P & Q

In other words, your "method" depends on already having the factors (P and Q).

CRGreathouse · 2020-08-10, 15:22

...so the "MILESTONE" is that, if you know the factorization, you can find it again very quickly?

ewmayer · 2020-08-10, 21:10

Quote:

Originally Posted by SarK0Y

for now, it's just a test mode, so it takes original P & Q

Well golly, my own top-sekrit factoring method for RSA-style moduli has that beat by a mile. You see, given a semiprime n = p*q, I only need *one* of p or q in order to quickly produce the other prime factor.

SarK0Y · 2020-08-11, 01:08

strictly speaking, it's not an actual factorization method, it's test bench to expose possible vectors of attack to crack IF.. so, yes == it takes P & Q to collect info for new methods. why "MILESTONE"? :) for instance, the're no division and no modular arithmetic, thereby test bench is rather fast. In fact, we use modular arithmetic for pseudorandom numbers, so it provides too wobbly ground to construct useful criteria + big matrices ain't good for multi-threaded solutions. in short, current methods already approached its deadline by algorithmic limits & hw ones as well.

CRGreathouse · 2020-08-11, 02:54

Quote:

Originally Posted by SarK0Y

strictly speaking, it's not an actual factorization method, it's test bench to expose possible vectors of attack to crack IF.

Could you give an example of what such a vector would look like?

Quote:

Originally Posted by SarK0Y

why "MILESTONE"? :) for instance, the're no division and no modular arithmetic, thereby test bench is rather fast.

Could you give an example of a similar algorithm that already does the same thing (or a comparable thing), but which uses heavier operations like division or modular arithmetic? (Not that those are particularly costly, but I digress.) It would help us understand what, exactly, you're trying to do.

Quote:

Originally Posted by SarK0Y

In fact, we use modular arithmetic for pseudorandom numbers, so it provides too wobbly ground to construct useful criteria + big matrices ain't good for multi-threaded solutions.

Are you saying

That your algorithm uses modular arithmetic, in particular for the generation of pseudorandom numbers (but I thought you said it didn't use modular arithmetic?), or
That some algorithms for generating pseudorandom numbers use modular arithmetic, and your method, not using modular arithmetic, is superior (but how does your method compare to generating pseudorandom numbers? seems like apples and oranges, or am I missing something?)

And what is this about big matrices?

Quote:

Originally Posted by SarK0Y

In short, current methods already approached its deadline by algorithmic limits & hw ones as well.

Current methods for what, exactly?

Till · 2020-08-11, 15:22

Quote:

Originally Posted by SarK0Y

Archive: https:// sourceforge . net /projects/fastprimecruncher/

Password for archive: ᬓꨒꛏ78��

SourceForge says "Malware detected. Download at own risk."

Somebody here with a virtual machine at hand including virus and malware scanner wants to try to open it?

Uncwilly · 2020-08-11, 15:32

Quote:

Originally Posted by Till

SourceForge says "Malware detected. Download at own risk."

Thanks for catching that. I broke the link. If someone want to get it they can do so with full knowledge.

kruoli · 2020-08-11, 15:57

Quote:

Originally Posted by Till

Somebody here with a virtual machine at hand including virus and malware scanner wants to try to open it?

The file contains:

Code:

.:
total 16K
drwxrwxrwx 1 oliver oliver 4.0K Aug 11 17:56 .
drwxrwxrwx 1 oliver oliver 4.0K Aug 11 17:56 ..
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 FastPrimeCruncher
-rwxrwxrwx 1 oliver oliver  15K Aug  9 20:49 MILESTONE.odt

./FastPrimeCruncher:
total 160K
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 .
drwxrwxrwx 1 oliver oliver 4.0K Aug 11 17:56 ..
drwxrwxrwx 1 oliver oliver 4.0K Jul 20 00:07 bin
-rwxrwxrwx 1 oliver oliver  23K Jul 25 22:20 BuildLog.txt
drwxrwxrwx 1 oliver oliver 4.0K Feb 20  2019 .clang
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 18:26 .codelite
-rwxrwxrwx 1 oliver oliver  287 Aug  3 00:33 compile_commands.json
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 18:26 Debug
-rwxrwxrwx 1 oliver oliver 1.1K Jul 19 23:59 FastPrimeCruncher.cbp
-rwxrwxrwx 1 oliver oliver  176 Jul 20 00:53 FastPrimeCruncher.layout
-rwxrwxrwx 1 oliver oliver 4.2K Aug  8 18:26 FastPrimeCruncher.mk
-rwxrwxrwx 1 oliver oliver 4.7K Aug  5 19:42 FastPrimeCruncher.project
-rwxrwxrwx 1 oliver oliver   39 Aug  8 18:26 FastPrimeCruncher.txt
-rwxrwxrwx 1 oliver oliver  594 Aug  8 06:01 FastPrimeCruncher.workspace
-rwxrwxrwx 1 oliver oliver  165 Jul 19 23:56 FastPrimeCruncher.workspace.layout
-rwxrwxrwx 1 oliver oliver  45K Aug  8 18:26 gears.cpp
-rwxrwxrwx 1 oliver oliver 5.2K Aug  4 00:29 headers.h
-rwxrwxrwx 1 oliver oliver 5.7K Feb 20  2019 konsole1.txt
-rwxrwxrwx 1 oliver oliver  14K Feb 20  2019 konsole.txt
-rwxrwxrwx 1 oliver oliver 2.4K Feb 20  2019 main0.cpp
-rwxrwxrwx 1 oliver oliver 1.8K Feb 20  2019 main1.cpp
-rwxrwxrwx 1 oliver oliver 4.4K Aug  8 17:50 main.cpp
-rwxrwxrwx 1 oliver oliver  267 Aug  8 18:26 Makefile
-rwxrwxrwx 1 oliver oliver 1.7K Aug  8 23:55 milestone.txt
-rwxrwxrwx 1 oliver oliver  11K Jul 28 04:56 out.txt
-rwxrwxrwx 1 oliver oliver   18 Aug  8 23:39 pswd.txt
drwxrwxrwx 1 oliver oliver 4.0K Jul 25 22:19 Release
-rwxrwxrwx 1 oliver oliver  581 Aug  8 18:14 run.gdb
-rwxrwxrwx 1 oliver oliver  193 Feb 20  2019 txt.txt

./FastPrimeCruncher/bin:
total 0
drwxrwxrwx 1 oliver oliver 4.0K Jul 20 00:07 .
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 ..
drwxrwxrwx 1 oliver oliver 4.0K Jul 20 00:47 Debug

./FastPrimeCruncher/bin/Debug:
total 0
drwxrwxrwx 1 oliver oliver 4.0K Jul 20 00:47 .
drwxrwxrwx 1 oliver oliver 4.0K Jul 20 00:07 ..

./FastPrimeCruncher/.clang:
total 0
drwxrwxrwx 1 oliver oliver 4.0K Feb 20  2019 .
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 ..

./FastPrimeCruncher/.codelite:
total 524K
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 18:26 .
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 ..
-rwxrwxrwx 1 oliver oliver 7.0K Aug  8 18:26 compilation.db
-rwxrwxrwx 1 oliver oliver  539 Jul 25 22:17 compile_commands.json
-rwxrwxrwx 1 oliver oliver 3.5K Aug  8 06:01 FastPrimeCruncher.session
-rwxrwxrwx 1 oliver oliver 300K Aug  8 18:26 FastPrimeCruncher.tags
-rwxrwxrwx 1 oliver oliver  156 Feb 20  2019 FastPrimeCruncher.workspace.someone
-rwxrwxrwx 1 oliver oliver 210K Aug  8 16:44 refactoring.db
-rwxrwxrwx 1 oliver oliver    3 Feb 20  2019 sftp-workspace-settings.conf
-rwxrwxrwx 1 oliver oliver   44 Feb 20  2019 subversion.conf
drwxrwxrwx 1 oliver oliver 4.0K Feb 20  2019 tabgroups
-rwxrwxrwx 1 oliver oliver  142 Feb 20  2019 .tern-project
-rwxrwxrwx 1 oliver oliver    3 Feb 20  2019 tweaks.conf
-rwxrwxrwx 1 oliver oliver    0 Feb 20  2019 valgrind.memcheck.supp

./FastPrimeCruncher/.codelite/tabgroups:
total 0
drwxrwxrwx 1 oliver oliver 4.0K Feb 20  2019 .
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 18:26 ..

./FastPrimeCruncher/Debug:
total 2.1M
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 18:26 .
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 ..
-rwxrwxrwx 1 oliver oliver    1 Aug  8 18:26 .d
-rwxrwxrwx 1 oliver oliver 594K Aug  8 18:26 FastPrimeCruncher
-rwxrwxrwx 1 oliver oliver 980K Aug  8 18:26 gears.cpp.o
-rwxrwxrwx 1 oliver oliver   50 Aug  8 18:26 gears.cpp.o.d
-rwxrwxrwx 1 oliver oliver 500K Aug  8 17:57 main.cpp.o
-rwxrwxrwx 1 oliver oliver   48 Aug  8 17:57 main.cpp.o.d

./FastPrimeCruncher/Release:
total 220K
drwxrwxrwx 1 oliver oliver 4.0K Jul 25 22:19 .
drwxrwxrwx 1 oliver oliver 4.0K Aug  8 23:55 ..
-rwxrwxrwx 1 oliver oliver    1 Jul 25 22:19 .d
-rwxrwxrwx 1 oliver oliver  73K Jul 25 22:19 FastPrimeCruncher
-rwxrwxrwx 1 oliver oliver 121K Jul 25 22:19 gears.cpp.o
-rwxrwxrwx 1 oliver oliver   53 Jul 25 22:19 gears.cpp.o.d
-rwxrwxrwx 1 oliver oliver  20K Jul 25 22:19 main.cpp.o
-rwxrwxrwx 1 oliver oliver   51 Jul 25 22:19 main.cpp.o.d

2020-08-09, 20:11	#1
SarK0Y Jan 2010 2×43 Posts	Brimstone for cracking RSA. (jk) Story of tails, windows and how it impacts integer factorization.. In other words, MILESTONE has been done :D From the very start of my journey to discover the innards of stubborn IF, the prime goal was to have developed binary-search-tree algos. At some point, it seemed utterly impossible. But here we go.. Actually, algo consists of three stages.. it picks initial (probable) Z’s (pZ_L and pZ_R) up (Z = P + Q, N = PQ). So, now algo needs to guess which one is closest to original Z. for pZ_L, it generates N_L which is closest to N from left/right and the same way for N_R of pZ_R. for N_R/L, it collects statistics of bit windows against N (their positions, widths..).. Window(N, EntryPoint, Width) == NOT Window(N_L, EntryPoint, Width). For instance, let Window(N, EntryPoint, Width) == “010”, then Window(N_L, EntryPoint, Width) == “101”. And now it’s possible to choose probable Z according collected statistics for given iteration. For tests, RSA-150 (https://en.wikipedia.org/wiki/RSA_numbers#RSA-150) has been taken, criterion to go left/right is widths of greatest windows. Output… test mode gets activated Wrong turn @ 1 Wrong turn @ 2 Wrong turn @ 3 Wrong turn @ 4 Wrong turn @ 5 Wrong turn @ 6 Wrong turn @ 7 Wrong turn @ 8 Wrong turn @ 9 Wrong turn @ 10 Wrong turn @ 11 Wrong turn @ 12 Wrong turn @ 13 Wrong turn @ 14 Wrong turn @ 15 Wrong turn @ 16 Wrong turn @ 17 Wrong turn @ 18 Wrong turn @ 19 Wrong turn @ 20 Wrong turn @ 21 Wrong turn @ 22 Wrong turn @ 23 Wrong turn @ 24 Wrong turn @ 25 Wrong turn @ 26 Wrong turn @ 27 Wrong turn @ 28 Wrong turn @ 29 Wrong turn @ 30 Wrong turn @ 31 Wrong turn @ 32 Wrong turn @ 33 Wrong turn @ 34 Wrong turn @ 35 Wrong turn @ 36 Wrong turn @ 37 Wrong turn @ 38 Wrong turn @ 39 Wrong turn @ 40* Wrong turns == 40 nice turns == 208 Total iterations == 248 In short, algo doesn’t do gaps (good and bad turns ain’t shuffled/mixed) even with such rather primitive criterion. Archive: https:// sourceforge . net /projects/fastprimecruncher/Mod note URL intentionally broken. Sourceforge reports it as malware. Password for archive: ᬓꨒꛏ78🁶 Last fiddled with by Uncwilly on 2020-08-11 at 15:30 Reason: Broke the URL

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fast Factoring and Cracking The RSA	Owl	Miscellaneous Math	11	2021-01-01 01:26
Pope "Deviled Eggs" Benedict, heaven help us for cracking such yolks	jasong	Soap Box	9	2013-03-17 03:28

2020-08-10, 04:21	#2
CRGreathouse Aug 2006 2²×1,493 Posts	Fantastic! Unfortunately, Aoki, Kida, Shimoyama, & Ueda already factored RSA-150, so it's not a good way to show that your method works. Could you demonstrate it with this smaller number, please? 3817396723515136582858035291731476702231874047478035390874743899933916107585885458479075057627686466112442032963859000272684225286856787555319737 I promise that it was (pseudo-)randomly generated* and that I've kept the factorization a secret (even from myself). This number isn't considered hard to factor, and so it won't of itself demonstrate a breakthrough, but it would make a better example. (Of course if you could factor such examples quickly enough it would suggest either collusion or a breakthrough, either in factorization or RNG cracking.) * Brent's XORGEN.

2020-08-10, 15:22	#5
CRGreathouse Aug 2006 2²×1,493 Posts	...so the "MILESTONE" is that, if you know the factorization, you can find it again very quickly?

2020-08-11, 01:08	#7
SarK0Y Jan 2010 2×43 Posts	strictly speaking, it's not an actual factorization method, it's test bench to expose possible vectors of attack to crack IF.. so, yes == it takes P & Q to collect info for new methods. why "MILESTONE"? :) for instance, the're no division and no modular arithmetic, thereby test bench is rather fast. In fact, we use modular arithmetic for pseudorandom numbers, so it provides too wobbly ground to construct useful criteria + big matrices ain't good for multi-threaded solutions. in short, current methods already approached its deadline by algorithmic limits & hw ones as well.