mersenneforum.org Milestone for cracking RSA. (jk)
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-09, 20:11 #1 SarK0Y     Jan 2010 32×7 Posts Milestone 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 = 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🁶 Last fiddled with by Uncwilly on 2020-08-11 at 15:30 Reason: Broke the URL
 2020-08-10, 04:21 #2 CRGreathouse     Aug 2006 592610 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, 10:32   #3
SarK0Y

Jan 2010

32×7 Posts

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

2020-08-10, 12:23   #4
Dr Sardonicus

Feb 2017
Nowhere

67368 Posts

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).

Last fiddled with by Dr Sardonicus on 2020-08-10 at 12:23 Reason: xifnig posty

 2020-08-10, 15:22 #5 CRGreathouse     Aug 2006 134468 Posts ...so the "MILESTONE" is that, if you know the factorization, you can find it again very quickly?
2020-08-10, 21:10   #6
ewmayer
2ω=0

Sep 2002
República de California

979110 Posts

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.

 2020-08-11, 01:08 #7 SarK0Y     Jan 2010 3F16 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.
2020-08-11, 02:54   #8
CRGreathouse

Aug 2006

10111001001102 Posts

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
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
2. 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?

2020-08-11, 15:22   #9
Till

"Tilman Neumann"
Jan 2016
Germany

3×139 Posts

Quote:
 Originally Posted by SarK0Y Archive: https:// sourceforge . net /projects/fastprimecruncher/ Password for archive: ᬓꨒꛏ78������

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

Last fiddled with by Uncwilly on 2020-08-11 at 15:32 Reason: Broke the URL

2020-08-11, 15:32   #10
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2×4,349 Posts

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.

2020-08-11, 15:57   #11
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

2·163 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Owl Miscellaneous Math 10 2020-09-09 19:52 jocelynl1204 Factoring 0 2018-10-12 11:56 tcharron PrimeNet 3 2013-08-29 06:44 jasong Soap Box 9 2013-03-17 03:28 tha Data 526 2010-11-23 00:09

All times are UTC. The time now is 17:16.

Tue Oct 20 17:16:33 UTC 2020 up 40 days, 14:27, 1 user, load averages: 2.33, 2.33, 2.38
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.40901440382003784, "perplexity": 17785.082315781347}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-45/segments/1603107874026.22/warc/CC-MAIN-20201020162922-20201020192922-00583.warc.gz"}