search

AdamWhiteHat / GNFS

A complete, proof-of-concept, C# implementation of the General Number Field Sieve algorithm for factoring very large semi-prime numbers. The focus was on readability and understandability of the code, not performance.
GNU General Public License v3.0
56 stars 13 forks source link

BUG: Application crashes with default values #17

Open JSchimmelpfennig opened 2 weeks ago

JSchimmelpfennig commented 2 weeks ago

Description Hi there and thank you for the hard work! I would really like to test the program out, but after cloning the whole repository and starting GNFS-master\GNFS-master\Binaries\Release\GNFS-Winforms.exe I get two errors.

Error/Exception Message Using default values and clicking on "increase" shows this message: System.NullReferenceException: Object reference not set to an instance of an object. at GNFS_Winforms.MainForm.btnIncreaseSmoothnessBound_Click(Object sender, EventArgs e) at System.Windows.Forms.Control.OnClick(EventArgs e) at System.Windows.Forms.Button.OnMouseUp(MouseEventArgs mevent) at System.Windows.Forms.Control.WmMouseUp(Message& m, MouseButtons button, Int32 clicks) at System.Windows.Forms.Control.WndProc(Message& m) at System.Windows.Forms.ButtonBase.WndProc(Message& m) at System.Windows.Forms.Button.WndProc(Message& m) at System.Windows.Forms.NativeWindow.Callback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam): ENCOUNTERED A UNTRAPPED THREAD EXCEPTION

Clicking on create, the program crashes and the output.log says: [243.2024 @ 08:54:08] Processing thread LAUNCHED. [243.2024 @ 08:54:08] [New factorization job creation initialization for N = 3218147...] [243.2024 @ 08:54:08] System.IO.FileNotFoundException: Could not load file or assembly 'ExtendedArithmetic.Polynomial, Version=2022.152.744.0, Culture=neutral, PublicKeyToken=null' or one of its dependencies. The system cannot find the file specified. File name: 'ExtendedArithmetic.Polynomial, Version=2022.152.744.0, Culture=neutral, PublicKeyToken=null' at GNFSCore.GNFS..ctor() at GNFSCore.GNFS..ctor(CancellationToken cancelToken, LogMessageDelegate logFunction, BigInteger n, BigInteger polynomialBase, Int32 polyDegree, BigInteger primeBound, Int32 relationQuantity, Int32 relationValueRange) at GNFS_Winforms.MainForm.<>cDisplayClass41_0.b0() at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx) at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx) at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state) at System.Threading.ThreadHelper.ThreadStart()

WRN: Assembly binding logging is turned OFF. To enable assembly bind failure logging, set the registry value [HKLM\Software\Microsoft\Fusion!EnableLog] (DWORD) to 1. Note: There is some performance penalty associated with assembly bind failure logging. To turn this feature off, remove the registry value [HKLM\Software\Microsoft\Fusion!EnableLog]. : CAUGHT A UNHANDLED APPLICATION EXCEPTION

Screenshots image

My goal here is to show my colleagues why we need in RSA a modulus $|n| \geq 3072$ bit and I would like to the factorization for small $n$ with your implementation.

Thank you!

AdamWhiteHat commented 2 weeks ago

The button "Increase" is intended to be pushed only after a factorization job has been created or loaded. I think this is a bug, in that the button should be disabled until those steps have been taken. So I have fixed this.

Regarding the second crash, yeah, this is a mistake on my part. This is because it is missing some .dll libraries it takes a dependency on. I don't know how I missed this, or what I was thinking, I should have realized the executable wasn't going to run correctly without those .dlls.

I went ahead and updated the GNFS-master\GNFS-master\Binaries\Release\ directory with the latest build that includes the disabling the Increase button until a factorization job is created, as mentioned above. I think the version that was there was a few versions out of date. This new version require .NET 5.0 or later. I hope that's okay. Youll notice there are a WHOLE LOT more files in that Release directory now. This is a result of using the new .NET 5.0 version. I wish it wasnt so, but I see no way around it. But just run the GNFS_Winforms.exe executable as before.

Since you cloned down the repository, you should be able to 'pull' the latest changes from the master branch to receive these changes.

Regarding modulus size: 3072 bit? As in semiprime contains some 924 digits? If yes, then that RSA number should be sufficiently secure, provided that the primes were picked at random and are not too close to each other. 2048 is a pretty common size that is considered secure. I will say my library has no hope for factoring a 3072 bit semiprime, or even a 1024 bit semiprime for that matter. In fact, my implementation is not fastest or most efficient factorization project out there. Its goal was to be readable and understandable, not necessarily efficient. The other factorization libraries that are efficient, have much of their critical areas written in assembly, and the rest in C++, so they are not exactly friendly for reading and understanding the algorithm.

Anyways, the state-of-the-art factorization project for factoring large semiprime numbers is CADO-NFS. If you are intending to do an serious factorization, you should consider using that.

JSchimmelpfennig commented 2 weeks ago

Thank you for fixing this so quickly!

I pulled the repository and exectuting GNFS-master\GNFS-master\Binaries\ReleaseGNFS_Winforms.exe works! I don't care if there are more files in there, new versions of the .NET framework are always better, right? ;)

NIST Special Publication 800-57 Part 1 Revision 5 - Recommendation for Key Management says, that $|n| \geq 3072$ is needed for 128 bit security and I just want to show my colleagues, that we can factorize smaller n (e.g. 128 bit) very fast with your application :)

I don't want to factorize a 3072 bit RSA modulus, but thank you for mentioning CADO-NFS, I will take a look that that as well :)

To make your application more easy to use, it might be helpful to describe or show the steps in screenshots or a small video how to factorize an example value for $n$. :)

I don't really understand how to use the application.

When I use $p = 59407, q = 53597$ and therefore $n = (p * q) = 3184036979$ and I insert $3184036979$ into the program, I have to click on 1) create, then save and then on 2) find relations, right? But this steps seems not to finish even though Relation value range is set to 1000 but it continues. Am I doing something wrong?

Output after 1):

Processing thread LAUNCHED.
    [New factorization job creation initialization for N = 3184036979...]
    　Polynomial constructed: 29791*X^3 + 961*X^2 + 31*X + 2295608816
    　Polynomial base: 31
    　Rational  Factor Base Bounds: Min: - Max: 50
    　Algebraic Factor Base Bounds: Min: - Max: 150
    　Quadratic Factor Base Bounds: Min: 170 Max: 1113
    　Saved prime factor base bounds.
    　Constructing new prime bases (- of 3)...
    　Completed rational prime base (1 of 3).
    　Completed algebraic prime base (2 of 3).
    　Completed quadratic prime base (3 of 3).
    　Constructing new factor bases (- of 3)...
    　Completed rational factor base (1 of 3).
    　Completed algebraic factor base (2 of 3).
    　Completed quadratic factor base (3 of 3).
    　Factor bases populated.
    　Relations container initialized. Target quantity: 60
Processing thread COMPLETED.
[New factorization job initialization complete]
NOTE: You should save your progress now.

Required smooth relations found before beginning matrix step: 65
Smooth relations target value: 65

Smooth relations currently loaded count: 0
Smooth relations saved counter: 0

quadraticFactorPair_Count: 10
PrimeIndxOf(quadraticBase_Max): 187

[Initialization took: 197 Milliseconds]
[Save progress task began...]
[Save progress task successfully completed]
[Saving took: 1 Milliseconds]

Output after 2) (cancelled manually after 52s):

    　B = 2130
    　SmoothRelations.Count: 3
    　B = 2131
    　SmoothRelations.Count: 3
    　B = 2132
    　SmoothRelations.Count: 3
    　B = 2133
    　SmoothRelations.Count: 3
    　B = 2134
    　SmoothRelations.Count: 3
    　B = 2135
    　SmoothRelations.Count: 3
    　B = 2136
    　SmoothRelations.Count: 3
    　B = 2137
    　SmoothRelations.Count: 3
    　B = 2138
    　SmoothRelations.Count: 3
    　B = 2139
    　SmoothRelations.Count: 3
    　B = 2140
    　SmoothRelations.Count: 3
    　B = 2141
    　SmoothRelations.Count: 3
    　B = 2142
    　SmoothRelations.Count: 3
    　B = 2143
    　SmoothRelations.Count: 3
    　B = 2144
    　SmoothRelations.Count: 3
    　B = 2145
    　SmoothRelations.Count: 3
    　B = 2146
    　SmoothRelations.Count: 3
    　B = 2147
    　SmoothRelations.Count: 3
    　B = 2148
    　SmoothRelations.Count: 3
    　B = 2149
    　SmoothRelations.Count: 3
    　B = 2150
    　SmoothRelations.Count: 3
    　B = 2151
    　SmoothRelations.Count: 3

    Sieving progress saved at:
       A = 1
       B = 2151

    　GenerateRelations: TargetQuantity = 65, ValueRange = 1001, A = 1, B = 2151, Max B = 2250
    　B = 2152
    　SmoothRelations.Count: 3
    　B = 2153
    　SmoothRelations.Count: 3
    　B = 2154
    　SmoothRelations.Count: 3
    　B = 2155
    　SmoothRelations.Count: 3
    　B = 2156
    　SmoothRelations.Count: 3
    　B = 2157
    　SmoothRelations.Count: 3
    　B = 2158
    　SmoothRelations.Count: 3
    　B = 2159
    　SmoothRelations.Count: 3
    　B = 2160
    　SmoothRelations.Count: 3
    　B = 2161
    　SmoothRelations.Count: 3
    　B = 2162
    　SmoothRelations.Count: 3
    　B = 2163
    　SmoothRelations.Count: 3
    　B = 2164
    　SmoothRelations.Count: 3
    　B = 2165
    　SmoothRelations.Count: 3
    　B = 2166
    　SmoothRelations.Count: 3
    　B = 2167
    　SmoothRelations.Count: 3
    　B = 2168
    　SmoothRelations.Count: 3
    　B = 2169
    　SmoothRelations.Count: 3
    　B = 2170
    　SmoothRelations.Count: 3
    　B = 2171
    　SmoothRelations.Count: 3
    　B = 2172
Processing thread COMPLETED.
Processing thread CANCELED.
　SmoothRelations.Count: 3

Sieving progress saved at:
   A = 1
   B = 2172

[Find relations task complete]

Required smooth relations found before beginning matrix step: 65
Smooth relations target value: 65

Smooth relations currently loaded count: 3
Smooth relations saved counter: 3

quadraticFactorPair_Count: 10
PrimeIndxOf(quadraticBase_Max): 187

[Find relations task took: 51.948 Seconds]

When I then follow steps 3 and 4 I get:

Processing thread LAUNCHED.
    [Matrix solve task starting up...]
    Total relations count: 3
    Relations required to proceed: 65
Processing thread COMPLETED.
[Matrix solve task complete]
[Matrix solve task took: 37 Milliseconds]
Processing thread LAUNCHED.
    [Find square root task starting up...]
    　
    　ƒ'(θ) = 89373*X^2 + 1922*X + 31
    　ƒ'(θ)² = 7987533129*X^4 + 343549812*X^3 + 9235210*X^2 + 119164*X + 961
    　ƒ'(θ)² ∈ ℤ[θ] = -1847042*X^2 - 615496340107313*X - 6618240215567
    　
    　ƒ'(m) = 85947066
    　ƒ'(m)² = 7386898154008356
    　
    　MonicPolynomial: X^3 + 924451*X^2 + 31*X + 2295608816
    　MonicPolynomialDerivative: 3*X^2 + 1848902*X + 31
    　MonicPolynomialDerivativeSquared: 9*X^4 + 11093412*X^3 + 3418438605790*X^2 + 114631924*X + 961
    　MonicPolynomialDerivativeSquaredInField: 854609651308*X^2 - 20631821363*X - 6366533596679087
    　ERROR: ALL RELATION SETS HAVE BEEN TRIED...?
    　If the number of solution sets (0) is low, you may need to sieve some more and then re-run the matrix solving step.
    　If there are many solution sets, and you have tried them all without finding non-trivial factors, then something is wrong...
    　
Processing thread COMPLETED.
[Find square root task complete]
[Find square root task took: 107 Milliseconds]
AdamWhiteHat commented 2 weeks ago

Try increasing the smoothness bound to 1600 or 5000 or so, and set the polynomial base to 90.