Trying to use rsacryptoserviceprovider to generate large primes

Question

3.00/5 (1 vote)

See more:

Code is below, basically I create an instance of the RSACryptoServiceProvider, export the Parameters and <try> to turn the P and Q parameters into numbers. P and Q are supposed to be primes but I must be doing something wrong because I get a lot of even numbers. The parameters, or so I read are Base64 Strings in little endian format. The sample posted requires a reference to System.Numerics.

VB

Option Strict On
Imports System.Security.Cryptography
Imports System.Xml
Imports System.IO
Imports System.Numerics
Public Class Form1
    WithEvents CBKeySizes As New ComboBox With {.Location = New Point(10, 10), .Size = New Size(120, 20)}
    WithEvents BTNGo As New Button With {.Location = New Point(150, 10), .Size = New Size(80, 20), .Text = "Generate"}
    WithEvents TXTPrimes As New TextBox With {.Location = New Point(10, 40), .Size = New Size(500, 200), .Multiline = True, _
                        .Anchor = CType(AnchorStyles.Top + AnchorStyles.Bottom + AnchorStyles.Left + AnchorStyles.Right, AnchorStyles), _
                        .ScrollBars = ScrollBars.Vertical}
    WithEvents CBreverse As New CheckBox With {.Checked = True, .Text = "Reverse Bytes ?", .Location = New Point(250, 10), .Size = New Size(120, 20)}
    Private Function ShowArray(inputArray() As Byte) As String
        Dim RetString As String = ""
        For Each by As Byte In inputArray
            RetString &= by.ToString("X2") & " "
        Next
        Return RetString
    End Function
    Private Function BArray_To_Decimal(InputArray() As Byte) As String
        Dim WorkArray() As Byte = InputArray
        If CBreverse.Checked Then Array.Reverse(WorkArray)
        Dim BigInt As BigInteger = New BigInteger(WorkArray)
        Return BigInt.ToString
    End Function
    Private Function BArray_To_Hex(InputArray() As Byte) As String
        Dim WorkArray() As Byte = InputArray
        If CBreverse.Checked Then Array.Reverse(WorkArray)
        Dim BigInt As BigInteger = New BigInteger(WorkArray)
        Return BigInt.ToString("x")
    End Function
    Private Sub BTNGo_Click(sender As System.Object, e As System.EventArgs) Handles BTNGo.Click
        TXTPrimes.Clear()
        Using rsa As New RSACryptoServiceProvider(CInt(CBKeySizes.Text))
            Dim Params As RSAParameters = rsa.ExportParameters(True)
            TXTPrimes.AppendText("P (Array  )   : " & ShowArray(Params.P) & vbNewLine)
            TXTPrimes.AppendText("P (Base 64)   : " & Convert.ToBase64String(Params.P) & vbNewLine)
            TXTPrimes.AppendText("P (Prime-Dec) : " & BArray_To_Decimal(Params.P) & vbNewLine)
            TXTPrimes.AppendText("P (Prime-Hex) : " & BArray_To_Hex(Params.P) & vbNewLine)
            TXTPrimes.AppendText(vbNewLine)
            TXTPrimes.AppendText("Q (Array  )   : " & ShowArray(Params.Q) & vbNewLine)
            TXTPrimes.AppendText("Q (Base 64)   : " & Convert.ToBase64String(Params.Q) & vbNewLine)
            TXTPrimes.AppendText("Q (Prime-Dec) : " & BArray_To_Decimal(Params.Q) & vbNewLine)
            TXTPrimes.AppendText("Q (Prime-Hex) : " & BArray_To_Hex(Params.Q) & vbNewLine)
        End Using
    End Sub

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
        Me.Size = New Size(550, 300)
        Me.Text = "Primes via RSA Key Generation"
        Me.Font = New Font("Consolas", 8)
        Me.Controls.Add(CBKeySizes)
        Me.Controls.Add(BTNGo)
        Me.Controls.Add(TXTPrimes)
        Me.Controls.Add(CBreverse)
        Using RSATest As New RSACryptoServiceProvider
            Dim legalKeySizes() As KeySizes = RSATest.LegalKeySizes
            If (legalKeySizes.Length > 0) Then
                For i As Integer = 0 To legalKeySizes.Length - 1 Step 1
                    For K As Integer = legalKeySizes(i).MinSize To legalKeySizes(i).MaxSize Step legalKeySizes(i).SkipSize
                        CBKeySizes.Items.Add(K)
                    Next
                Next
                CBKeySizes.SelectedIndex = 0
            Else
                MessageBox.Show("Fatal Error getting Legal Key Sizes", "Cannot Continue", MessageBoxButtons.OK, MessageBoxIcon.Stop)
                End
            End If
        End Using
    End Sub
End Class

What I have tried:

Code pasted in question, hoping someone can show me where I am malfunctioning.

Posted 27-May-16 8:54am

zomalaja

Updated 27-May-16 17:42pm

Add a Solution

Comments

Sergey Alexandrovich Kryukov 27-May-16 15:51pm

First of all, if your problem is purely remaining, why do you show some code contaminated with totally irrelevant Form class, System.IO, System.XML and other garbage? Perhaps if you remove all unrelated stuff and create a really focused code sample, some members will volunteer to read it.
—SA

zomalaja 27-May-16 17:15pm

Maybe because what I posted can be copied and pasted AS IS into a new Windows Forms Project and run. I am so sorry for including a few irrelevant lines left over from the prior version that used XMLKeys. I also did not realize how incredibly huge the code example was, all 71 lines. Perhaps you can show me some hints as to how to trim this down until it meets the criteria of a "really focused code sample" as well as explaining what "if your problem is purely remaining" means. Yes the problem remains. Is is because the exported parameters are more than just base64 strings representing the numbers ? Is it because I am not converting them correctly ? I don't know, which is why I asked the question.

Sergey Alexandrovich Kryukov 27-May-16 18:27pm

It's a good idea to develop code sample focusing on just one problem. First of all, it often helps to figure out the problem by yourself, if not, the comprehensive sample which nearly immediately can be copied and tested can be published.
—SA

Sergey Alexandrovich Kryukov 27-May-16 18:41pm

As far as I understand, you do the following:
1) Create an instance of RSACryptoServiceProvider with given key size. Everything else is supposed to be auto-generated
2) Export and instance of RSAParameters structure.
3) Out of 8 parameters, look at only two of them P and Q.
So, your question is reduced to writing one trivial function returning either RSAParameters or structures with just P and Q members. Plus something to represent P and Q. As everything above is trivial, your problem would be in representation of P and Q. Indeed, how do you know that you obtain any even numbers?
—SA

zomalaja 27-May-16 19:07pm

"Indeed, how do you know that you obtain any even numbers?"

I don't know how to answer that without sounding insulting, so I will preface my response by saying I don't mean to be insulting.

When the decimal number ends in 0,2,4,6, or 8 It is an even number and thus it is not a prime number.

Sergey Alexandrovich Kryukov 27-May-16 20:15pm

I cannot be insulted, by definition, with such things. You did not understand what I said. I did not say a word about prime numbers. It's quite obvious that an even number is not a prime number. :-)

If you read my comment again, you will see "how do you know that you obtain any even numbers?" In the very beginning, you obtain an array of bytes. In that array, there is no such thing as decimal digits 0, 2, 4 or 8 (by the way, one prime number ends with 2). These digits are the artifact of decimal (string) representation of data. Now, let me see how you obtain it... Okay, you use BigInteger, and you initialize it by calling the constructor accepting an array of bytes. By doing so, you silently assume that the RSAParameters structure uses the same bitwise representation of big integer as System.Numeric.BigInteger. Yes, this assumption is quite natural, but to me, it needs some proof. I'm not saying it's wrong, it's just the only point I have some doubt at this moment. We both don't know what is wrong in your code. The description of RSA algorithm really says that these two parameters are prime numbers. I only know that the documentation on this constructor says that it's assumed that the parameter, the array of bytes is assumed to come in little endian order. And I did not reproduce your experiment...

By the way, one more thing: what values of size did you use in SACryptoServiceProvider constructor call?

—SA

zomalaja 27-May-16 22:43pm

Yes the number two (2) is a prime number, saying it ends with 2 is a bit misleading in the context of RSA values for P & Q. The key sizes are obtained in the MyBase.load Subroutine from the RSA.LegalKeySizes property and defaults to the lowest value, which is 384 (bits) on my computer. For me it goes as high as 16384 bits but I think that takes much longer than I care to wait for anything. The time required vs Key Size appears to increase exponentially, I made a graph but I don't see any way to include an image.

Sergey Alexandrovich Kryukov 27-May-16 23:31pm

I just performed the experiment, just seconds ago.

It confirms that my considerations that your assumption on the use of BigInteger are correct, but doesn't proof any representation of numeric values of P and Q. By RSA algorithm these parameters are supposed to be correct.

I reproduced appearance of both even and odd BigInteger values if I pass P or Q to BigInteger constructor. And there are approximately equal ratio of odd and even, as if the numbers was random.

Interestingly, I hypothesized that bytes should come in reverse order. I inverted the byte array and found that then BigInteger values become all odd.

By they way, I used more correct BigInteger.IsEven property.

I did not check up that the values interpreted this way are prime numbers or not. It is quite possible but would take more time, considering minimal value of legal key sizes. If you want to continue this experiment, you can do it using BigInteger division, but it will take finding all prime numbers less than your parameters.

Anyway, my experiment provides the evidence that you should blame your interpretation of P and Q arrays as numeric values. Also, it makes it very likely that the representation is the inverted array relative to the arrays assumed by BigInteger, but I don't have 100% evidence at this moment.

—SA

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2016-05-27T17:42:00

Sorry for the lack of comprehensive answer. But I can suggest what you can do.

Please see my comments to the question, all of them. In my last comment, I described my experiment following your idea, which provides a pretty strong evidence that the problem you observed is related to your wrong assumption that numeric interpretation of P and Q parameters, which are array of bytes, is the same as the interpretation used to initialize System.Numeric.BigInteger. I think that good chances are, the interpretation will match, for non-negative numbers, if you invert the array of byte. I don't have any proof (theoretically speaking, there can be many different interpretations), but it's unlikely that any other options could be used.

If you really want to dig into it, you need to expect the source code of RSACryptoServiceProvider and relevant dependencies of it. Unfortunately, Microsoft documentation is not detailed enough. (I would not probably need BigInteger source code.) You can access .NET FCL source code here: Reference Source[^].

Also, I just found one article on the topic, did not read it yet. Please see: .NET 4 BigInteger and RSA Signature and Encryption[^].

Generally, this class is not really intended to provide the source of prime number, but I must admit that your idea is very good, as the class provides decent performance. You only need to find out correct numeric interpretation or, better yet, the whole arithmetic of all operations performed directly on arrays of bytes.

—SA