mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-04-01, 13:36   #1
naturevault
 
Apr 2021

2·3 Posts
Default Do easy to factor semi-primes exist?

I am working on a "cryptocurrency"-like proof of work that uses factoring large numbers as a proof of work. You can review the archive of it here if you want: MODERATOR NOTE: link removed

Basically a user generates a private key, then hashes it using some algorithm like sha-2 or sha-3 to get a public key. They then hash this public key with something like skien-1024 to get a large random number (and truncate to a given acceptable length). They then provide a prime factor of this number that is between 7/16ths and 1/2 the length of the number. So for the network to verify the PoW, they do a primality check of the factor, and divide the large number by the proposed factor. If it checks out, it is a valid proof of work (and of course the person who generated the challenge is the only one who can spend it because they are the only one that knows the private key). We would start around 140 or 150 digit numbers so people can complete a proof of work in about a week with a decent computer.

Is there any potential attack vectors to this method? My thought is one possibility is that someone generates mass amounts of numbers looking for one that is "easy to factor". But my gut tells me that if there exists a prime factor in the number that is between 7/16th and 1/2 of the digit length of the number, then it is not easy to factor generally. Also one would need to factor it to determine whether it is easy to factor, correct? Of course you can do checks to the number like primality checks but my point is, if it does indeed contain a prime factor of said length, then no "testing" would be able to determine if this number with said prime factor is easier than another number with said prime factor without factoring them, correct?

Another question I have is; could factoring algorithms be modified to do this challenge significantly faster than a typical GNFS or RSA algorithm, since only 1 factor is needed, or would you just run it through our typical programs and see if it returns a factor of required length?

Thanks.

Last fiddled with by Dr Sardonicus on 2021-04-01 at 14:01
naturevault is offline   Reply With Quote
Old 2021-04-01, 14:12   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

If large enough quantum computers come to pass, then all numbers of a certain size will be easy to factor. This size will depend on various factors of the quantum computer, but in the worst case (for you -- best case for the person factoring) an n-qubit computer can factor a number up to 2^(n-1) or so.

There's a huge speedup to be gained if a person is factoring many numbers at once, so your security margin has to be wide enough to account for this.

Integer factorization is an area of active research, so you should be prepared for major advances that could reduce your security margin at any time.

I would not base a cryptocurrency on integer factorization, there are just too many risks. (Selfishly, I hope you do -- it would increase the incentive to do research in this area!)
CRGreathouse is offline   Reply With Quote
Old 2021-04-01, 14:25   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by naturevault View Post
Basically a user generates a private key, then hashes it using some algorithm like sha-2 or sha-3 to get a public key. They then hash this public key with something like skien-1024 to get a large random number (and truncate to a given acceptable length). They then provide a prime factor of this number that is between 7/16ths and 1/2 the length of the number. So for the network to verify the PoW, they do a primality check of the factor, and divide the large number by the proposed factor. If it checks out, it is a valid proof of work (and of course the person who generated the challenge is the only one who can spend it because they are the only one that knows the private key). We would start around 140 or 150 digit numbers so people can complete a proof of work in about a week with a decent computer.

Is there any potential attack vectors to this method?
Yes, your users have too much flexibility. They could generate numbers until they find one with enough small factors (< 30 digits) to make finding the big one easy.
CRGreathouse is offline   Reply With Quote
Old 2021-04-01, 19:13   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×3×11×83 Posts
Default

Trivial question to answer.

For The Codebook challenge back in 1999 I created a RSA modulus which could have been factored much more easily than the GNFS actually used to solve the problem.

My evil sense of humour led me to produce primes which were just slightly larger than I thought that anyone would use P \pm 1 to discover.

Last fiddled with by xilman on 2021-04-01 at 19:14 Reason: Italicise
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Frobenius and semi-prime testing paulunderwood Number Theory Discussion Group 12 2018-11-09 07:07
find very easy twin prime in the infamy twin primes hal1se Miscellaneous Math 13 2018-11-05 16:34
Semi-prime factorization conjecture Alberico Lepore Alberico Lepore 7 2018-02-16 08:27
Does God exist? mfgoode Soap Box 194 2007-01-18 20:49
Semi-automated P-1 testing GP2 Marin's Mersenne-aries 2 2003-09-29 19:01

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


Sun Oct 24 07:45:14 UTC 2021 up 93 days, 2:14, 0 users, load averages: 1.09, 1.03, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.