mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Brimstone for cracking RSA. (jk) (https://www.mersenneforum.org/showthread.php?t=25822)

 SarK0Y 2020-08-09 20:11

Brimstone for cracking RSA. (jk)

[CENTER][COLOR=#000000][FONT=&quot][B] Story of tails, windows and how it impacts integer factorization.. [/B][/FONT][/COLOR]
[COLOR=#000000][FONT=&quot][B]In other words, MILESTONE has been done :D[/B][/FONT][/COLOR][/CENTER]
[LEFT][COLOR=#000000][FONT=&quot]
[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]From the very start of my journey to discover the innards of stubborn IF, the prime goal was to have [/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]developed binary-search-tree algos. At some point, it seemed utterly impossible. But here we go..[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]
[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Actually, algo consists of three stages..[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]
[/FONT][/COLOR][/LEFT]
[LIST][*]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.[/LIST][LIST][*] 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.[/LIST][LIST][*] for N_R/L, it collects statistics of bit windows against N (their positions, widths..)..[/LIST][LEFT][COLOR=#000000][FONT=&quot]
[/FONT][/COLOR][/LEFT]
[CENTER][COLOR=#000000][FONT=&quot]Window(N, EntryPoint, Width) == NOT Window(N_L, EntryPoint, Width).[/FONT][/COLOR][/CENTER]
[LEFT][COLOR=#000000][FONT=&quot]
[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]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.[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]
[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]For tests, RSA-150 ([URL]https://en.wikipedia.org/wiki/RSA_numbers#RSA-150[/URL]) has been taken, criterion to go left/right is widths of greatest windows. Output…[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]
[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot] test mode gets activated[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 1[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 2[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 3[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 4[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 5[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 6[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 7[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 8[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 9[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 10[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 11[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 12[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 13[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 14[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 15[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 16[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 17[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 18[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 19[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 20[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 21[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 22[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 23[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 24[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 25[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 26[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 27[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 28[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 29[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 30[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 31[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 32[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 33[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 34[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 35[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 36[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 37[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 38[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Wrong turn @ 39[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot][B][COLOR=#ff0000][COLOR=red]Wrong turn @ 40[/COLOR][/COLOR][/B][/FONT][/COLOR]
[COLOR=#000000][FONT=&quot][B][COLOR=#ff0000][COLOR=red]Wrong turns == 40[/COLOR][/COLOR][/B][/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]nice turns == 208[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Total iterations == 248[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]
[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]In short, algo doesn’t do gaps (good and bad turns ain’t shuffled/mixed) even with such rather primitive criterion.[/FONT][/COLOR]
[COLOR=#000000][FONT=&quot]Archive: https:// sourceforge . net /projects/fastprimecruncher/[/FONT][/COLOR][FONT="Arial Black"][COLOR="Red"]Mod note URL intentionally broken. Sourceforge reports it as malware.[/COLOR][/FONT]
[COLOR=#000000][FONT=&quot]Password for archive: ᬓꨒꛏ78🁶
[/FONT][/COLOR][/LEFT]

 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=CRGreathouse;553095]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

[/QUOTE]
for now, it's just a test mode, so it takes original P & Q :smile::blush::cmd::rolleyes:

 Dr Sardonicus 2020-08-10 12:23

[b][color=red]MODERATOR NOTE: Thread moved to Miscellaneous Math[/color][/b]
[QUOTE=SarK0Y;553107]for now, it's just a test mode, so it takes original P & Q :smile::blush::cmd::rolleyes:[/QUOTE]
In other words, your "method" depends on already having the factors (P and Q).
:tank:

 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=SarK0Y;553107]for now, it's just a test mode, so it takes original P & Q :smile::blush::cmd::rolleyes:[/QUOTE]

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=SarK0Y;553192]strictly speaking, it's not an actual factorization method, it's test bench to expose possible vectors of attack to crack IF.[/QUOTE]

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

[QUOTE=SarK0Y;553192]why "MILESTONE"? :) for instance, the're no division and no modular arithmetic, thereby test bench is rather fast.[/QUOTE]

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=SarK0Y;553192]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.[/QUOTE]

Are you saying
[LIST=1][*] 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?)[/LIST]
And what is this about big matrices?

[QUOTE=SarK0Y;553192]In short, current methods already approached its deadline by algorithmic limits & hw ones as well.[/QUOTE]

Current methods for what, exactly?

 Till 2020-08-11 15:22

[QUOTE=SarK0Y;553061][COLOR=#000000][FONT=&quot]Archive: https:// sourceforge . net /projects/fastprimecruncher/[/FONT][/COLOR]
[LEFT] [COLOR=#000000][FONT=&quot]Password for archive: ᬓꨒꛏ78������
[/FONT][/COLOR][/LEFT]
[/QUOTE]

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=Till;553292]SourceForge says "Malware detected. Download at own risk."[/QUOTE]
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=Till;553292]Somebody here with a virtual machine at hand including virus and malware scanner wants to try to open it?[/QUOTE]

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[/CODE]

All times are UTC. The time now is 02:07.