RSA cipher module

[Keya]

lol, if somebody can write faster code than wilberts x86/x64 routines i want their name, number, address, mothers maiden name and 3-digit CVV. some of his optimizations are so subtle but super clever, i try my best to read each line to see what he's doing rather than just look at them as a blackbox function. hey im here to learn!!!

[Crusiatus Black]

I'm sorry to bump this, but aren't the public keys not rather tiny? I'm not used to this implementation of RSA encryption, is there a way to get a larger output for the public key?

[coco2]

Do you mean the public exponent is $010001? I thought that was standard?

[Crusiatus Black]

Do you mean the public exponent is $010001? I thought that was standard?

Okay please explain to me if you wish. What is the public 'key' part, the private 'key' part? The key generation now produces the same private key every time on my end.

[coco2]

I'm at work at the moment so I don't have access to my code. Can you provide any code example? If you run the module just by itself, you can see if generates a different key each time.

[Crusiatus Black]

I'm at work at the moment so I don't have access to my code. Can you provide any code example? If you run the module just by itself, you can see if generates a different key each time.

I'll try to get to that as soon as possible. The thing I struggle with is getting a public and private key from it, not only a private key. Could you tell me what part is the public key and what part is the private key? I figured the public exponent was the public key, the private exponent and modulus are the private key, correct? Shouldn't the pubic and private key be different each time you generate a key?

[coco2]

Ok I see

The public key is (n,e)
The private key is (n,d)

n--> Modulus.BigInt::BigInt ; public
e--> PublicExponent.BigInt::BigInt ; $010001
d--> SecretExponent.BigInt::BigInt ; private


So for example

e: 10001
n: AFA5859866551AA263C7ACC5D34333FC05EF8DF675DD7570A84B90F818E070602F642AF3F7C28F
CBB6FFAE734841EA8C4AB2E0C02B4734BE40ECD8D86C7EF2C52135A359EBCAD05581B5550718BF7F
2BE36D659A4888C64E7EFE6BA0DD7C6B0C7371A17B9AC1D1975BA2E765525855C8708C049AF2662F
8038AE50EBF0F576A7
d: 9D304A209AE3EA940D2BB2A8CF69C2E9F5FDEE53F4231E6895941AC68CACBEA4B584B513E45450
0F8553C7B10FA73DDA133785FF343BE32DA838CDCED139C2D3BEE93C9787CB21E55FD9AD41DCD45
17FC3CB91420F8FBF9FE3FEB2A25AB3B40C09B91D482B1C4CA93B24124F73666CAD08A2E97545CD3
816D1CE79E74B6524E1

See here for where I got a lot of info: http://www.di-mgt.com.au/rsa_alg.html

Here is a key generator:

Code: Select all

EnableExplicit

XIncludeFile("cc2rsa.pbi")

#WindowTitle = "RSA Key Generator"
#MainWindow = 0

Enumeration ; Gadgets
  #txtBitSize
  #cboBitSize
  #btnGenerate
  #edtOutput
EndEnumeration

Structure ThreadParameters
  ThreadID.i
  Keysize.i
  Key.Cc2RSA::RSAKeyPair
  Processing.i
EndStructure

Define.i Quit=#False
Define.i wEvent
Define.Cc2RSA::RSAKeyPair K
Define.s OutputTextLine=""
Define.ThreadParameters P


Procedure Thread_GenerateKey(*P.ThreadParameters)
  Cc2RSA::GenerateKeyPair(*P\Key,*P\Keysize)
  *P\Processing=2 ;complete
EndProcedure

OpenWindow(#MainWindow, 0, 0, 400, 400, #WindowTitle, #PB_Window_SystemMenu | #PB_Window_MinimizeGadget | #PB_Window_ScreenCentered)

CreateStatusBar(0, WindowID(#MainWindow))
AddStatusBarField(#PB_Ignore)
StatusBarText(0, 0, "Ready")

TextGadget(#txtBitSize, 10, 10, 80, 20, "Key size (bits):")
ComboBoxGadget(#cboBitSize, 95, 10, 80, 20)
AddGadgetItem(#cboBitSize, -1, "1024")
AddGadgetItem(#cboBitSize, -1, "2048")
AddGadgetItem(#cboBitSize, -1, "3072")
AddGadgetItem(#cboBitSize, -1, "4096")
SetGadgetState(#cboBitSize, 1) ; select 2048
ButtonGadget(#btnGenerate, 240, 10, 140, 25, "Generate")
EditorGadget(#edtOutput, 10, 40, 380, 330, #PB_Editor_ReadOnly | #PB_Editor_WordWrap)
CompilerIf #PB_OS_Windows Or #PB_OS_Linux ; not supported on Mac
  SetGadgetColor(#edtOutput, #PB_Gadget_BackColor, $000000)
  SetGadgetColor(#edtOutput, #PB_Gadget_FrontColor, $00F000)
CompilerEndIf
While WindowEvent() : Wend

Repeat
  Delay(10)
  wEvent = WindowEvent()
  If P\Processing=2 ; processing has finished
    OutputTextLine="Public exponent: " + BigInt::GetHex(P\Key\PublicExponent)
    AddGadgetItem(#edtOutput, -1, OutputTextLine)
    OutputTextLine="Modulus: " + BigInt::GetHex(P\Key\Modulus)
    AddGadgetItem(#edtOutput, -1, OutputTextLine)
    OutputTextLine="Private exponent: " + BigInt::GetHex(P\Key\SecretExponent)
    AddGadgetItem(#edtOutput, -1, OutputTextLine)    
    StatusBarText(0, 0, "Ready")
    P\Processing=0
  EndIf
  Select wEvent
    Case #PB_Event_RightClick

    DisplayPopupMenu(0, WindowID(#MainWindow))
    Case #PB_Event_Gadget
      Select EventGadget()
        Case #btnGenerate
          If P\Processing=0 ; make sure not to create multiple threads
            P\Keysize=Val(GetGadgetText(#cboBitSize))
            P\Processing=1          
            ClearGadgetItems(#edtOutput)
            OutputTextLine="Generating " + P\Keysize + " bit key pair..."
            AddGadgetItem(#edtOutput, -1, OutputTextLine)
            StatusBarText(0, 0, "Calculating...")
            While WindowEvent() : Wend
            P\ThreadID=CreateThread(@Thread_GenerateKey(), P)
          EndIf
      EndSelect
  EndSelect
Until wEvent = #PB_Event_CloseWindow Or Quit

Don't forget to set #BigIntBits to 4096 otherwise you'll get weird results for 4096 bit operations.

[Crusiatus Black]

Yes! Thank you, it's all clear now to me. I'm loving your contribution, thanks again!

At first, I thought the modulus was part of the private key together with the private exponent.

[coco2]

Thanks, it wasn't easy but I really wanted to see a fast PureBasic implementation working so I spent weeks working it out.

[Crusiatus Black]

Thanks, it wasn't easy but I really wanted to see a fast PureBasic implementation working so I spent weeks working it out.

It payed off beautifully, thank you and Wilbert!

[Crusiatus Black]

I have one more question; Is it possible to encrypt a simple buffer with RSAProcessRaw? It now expects a BigInt for both the input and output (which is logical to me), but it would be nice to be able to simply provide an input and output buffer.

[Crusiatus Black]

I have one more question; Is it possible to encrypt a simple buffer with RSAProcessRaw? It now expects a BigInt for both the input and output (which is logical to me), but it would be nice to be able to simply provide an input and output buffer.

I solved it by converting a 512 bit buffer to hex, load it as BigInt and throw it into RSA. Works like a charm!

[Keya]

does anyone have code for saving and reading the three key components as binary files? (so that for example a decrypt-only program only needs 2 of the 3 key components - private and modulus, but not public... or perhaps ive got that backwards!). im guessing it's fairly straight forward but im a bit confused by the bigint structure

[wilbert]

im a bit confused by the bigint structure

It's just a little endian number like Long or Quad, only bigger.
For saving to a file you could just use WriteData with the right amount of bytes from the address of the BigInt value.
For reading I would recommend to load the data first to memory and then use BigInt::LoadValue to load the value from memory.

[Keya]

ahhh I think i get it now, thankyou wilbert!

Code: Select all

 Protected.RSAKeyPair K
...
 ShowMemoryViewer(K\SecretExponent, BigInt::NumberSize(K\SecretExponent))   ;e
 ;ShowMemoryViewer(K\Modulus, BigInt::NumberSize(K\Modulus))                ;n
 ;ShowMemoryViewer(K\PublicExponent, BigInt::NumberSize(K\PublicExponent))  ;d

@coco2 we should be using PB's CryptRandom() instead of Random() for this!
It was super easy to switch over and speed seems the same:
- add OpenCryptRandom() at start and CloseCryptRandom() after use
- text-replace the two RandomData() calls to CryptRandomData()
- text-replace the one Random() call to CryptRandom()
(CryptRandom() doesnt support the Minimum parameter like Random() does, but thats ok for this because youre only using the Maximum parameter which they both support)