mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-08-09, 20:11   #1
SarK0Y
 
SarK0Y's Avatar
 
Jan 2010

32·7 Posts
Default 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
SarK0Y is offline   Reply With Quote
Old 2020-08-10, 04:21   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2020-08-10, 10:32   #3
SarK0Y
 
SarK0Y's Avatar
 
Jan 2010

32·7 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
SarK0Y is offline   Reply With Quote
Old 2020-08-10, 12:23   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·5·233 Posts
Default

MODERATOR NOTE: Thread moved to Miscellaneous Math
Quote:
Originally Posted by SarK0Y View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2020-08-10, 15:22   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

...so the "MILESTONE" is that, if you know the factorization, you can find it again very quickly?
CRGreathouse is offline   Reply With Quote
Old 2020-08-10, 21:10   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1151810 Posts
Default

Quote:
Originally Posted by SarK0Y View Post
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.
ewmayer is offline   Reply With Quote
Old 2020-08-11, 01:08   #7
SarK0Y
 
SarK0Y's Avatar
 
Jan 2010

32×7 Posts
Default

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.
SarK0Y is offline   Reply With Quote
Old 2020-08-11, 02:54   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by SarK0Y View Post
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 View Post
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 View Post
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 View Post
In short, current methods already approached its deadline by algorithmic limits & hw ones as well.
Current methods for what, exactly?
CRGreathouse is offline   Reply With Quote
Old 2020-08-11, 15:22   #9
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×11×19 Posts
Default

Quote:
Originally Posted by SarK0Y View Post
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?

Last fiddled with by Uncwilly on 2020-08-11 at 15:32 Reason: Broke the URL
Till is offline   Reply With Quote
Old 2020-08-11, 15:32   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

207078 Posts
Default

Quote:
Originally Posted by Till View Post
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.
Uncwilly is online now   Reply With Quote
Old 2020-08-11, 15:57   #11
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

307 Posts
Default

Quote:
Originally Posted by Till View Post
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
kruoli is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fast Factoring and Cracking The RSA Owl Miscellaneous Math 10 2020-09-09 19:52
P-1 Milestone jocelynl1204 Factoring 0 2018-10-12 11:56
Another milestone! tcharron PrimeNet 3 2013-08-29 06:44
Pope "Deviled Eggs" Benedict, heaven help us for cracking such yolks jasong Soap Box 9 2013-03-17 03:28
New milestone tha Data 526 2010-11-23 00:09

All times are UTC. The time now is 06:00.

Thu Oct 1 06:00:35 UTC 2020 up 21 days, 3:11, 0 users, load averages: 1.68, 1.69, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.