RSA cipher module

[coco2]

Here is my pure PB RSA cipher module for all platforms.
Requires wilbert's bigint module: http://www.purebasic.fr/english/viewtop ... 12&t=61309

You can run the module to see it do a self test which demonstrates 4096 key generation and raw encrypt/decrypt.

Release history:
0.9 - 2014-Oct-03 - initial pre-release (WIP) no key generation or decrypt
1.0 - 2014-Dec-01 - first functional release, renamed file to cc2rsa.pbi
1.1 - 2014-Dec-17 - speed optimisations by wilbert, switch to little endian quad storage
1.2 - 2015-Feb-18 - now uses wilbert's bigint module (much faster)
1.3 - 2016-Mar-15 - key generation added
1.4 - 2016-Mar-16 - first complete release, raw encrypt/decrypt added
1.5 - 2016-Mar-17 - added optimisation for generating keys, other simplifications. Now generates 4096 bit keys 10 times faster.
1.6 - 2016-Jul-13 - Uses CryptRandom() instead of just Random() in key generation

Code: Select all

; cc2rsa.pbi==================================================================================================================================================
; PureBASIC RSA Cipher module
; Module version: 1.6
; Platform: Windows, Linux, Mac
; CPU architechtures: x86, x64
; Requirements: bigint.pbi - see notes
; Developed on: PB 5.41 LTS (x64); Windows 7 x64
; Author: Coco2
; Thanks to: wilbert
; Created:  17-Jun-2014
; License: open (no restrictions)
; Release history:
;   0.9    - 2014-Oct-03 - initial pre-release
;   1.0    - 2014-Dec-01 - first functional release, renamed file to cc2rsa.pbi
;   1.1    - 2014-Dec-17 - speed optimisations by wilbert, switch to little endian quad storage
;   1.2    - 2015-Feb-18 - now uses wilbert's bigint module (much faster)
;   1.3    - 2016-Mar-15 - key generation added
;   1.4    - 2016-Mar-16 - first complete release, raw encrypt/decrypt added
;   1.5    - 2016-Mar-17 - added optimisation for generating keys, other simplifications. Now generates 4096 bit keys 10 times faster.
;   1.6    - 2016-Jul-13 - Uses CryptRandom() instead of just Random() in key generation
;
; Provided "as is" with no warranty and no liability.
;
; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
; IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
; LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
; SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
; CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
; POSSIBILITY OF SUCH DAMAGE.
;
;
; Notes:
; 1. The authors/copyright holder(s) of this module are not affiliated with the PureBasic software authors/copyright holders.
;
; 2. Wilbert's bigint module:
;    http://www.purebasic.fr/english/viewtopic.php?f=12&t=61309
;    *** Note: remember to set #BigIntBits to the highest setting you want to use, eg- 4096
;
; 3. This module is still in an early testing phase. For production purposes use an existing security package.
;
; ============================================================================================================================================================
; Further reading and credits:
; 
; - RFCs 2313, 2437, 3447
; - Implementing SSL / TLS Using Cryptography and PKI (ISBN: 978-0-470-92041-1)
; - SCV Cryptomanager (test keys) http://cryptomanager.com/tv.html
; - RSA Algorithm http://www.di-mgt.com.au/rsa_alg.html
;
; ============================================================================================================================================================

;- Module includes

#BigIntLocation = ""

XIncludeFile(#BigIntLocation + "bigint.pbi")

DeclareModule Cc2RSA
  
  ;- Structures
  
  Structure RSAKeyPair
    ; Public key: N,e
    ; Private key: N,d
    KeySize.i
    ; Source values
    p.BigInt::BigInt
    q.BigInt::BigInt
    Phi.BigInt::BigInt
    ; Keypair ((N, e), d)
    ; The public keypair is (N,e)
    ; The private keypair is (N,d)
    Modulus.BigInt::BigInt ; N - public
    PublicExponent.BigInt::BigInt ; e - $010001
    SecretExponent.BigInt::BigInt ; d - private
  EndStructure
  
  ;- Procedure declares
  
  Declare.i GenerateKeyPair (*k.RSAKeyPair, bits.i=2048)
  Declare.i RSAProcessRaw (*Output.BigInt::BigInt, *Input.BigInt::BigInt, *K.RSAKeyPair, Key.i = 0)
  Declare SelfTest()
  
EndDeclareModule

Module Cc2RSA
  
  CompilerIf #PB_Compiler_IsMainFile
    EnableExplicit
  CompilerEndIf
  
  ;- Internal Procedures
  
  Procedure.i Composite(*n.BigInt::BigInt)
    ; Checks if a BigInt is composite by trial division
    ; Returns 0 = possibly prime, 1 = composite
    Restore PrimeLookup
    Protected.i Result=0
    Protected.i a0
    Protected.q a1
    Protected.BigInt::BigInt n0, n1, n2
    For a0 = 1 To 1000
      Read.i a1
      BigInt::SetValue(n0, a1)
      BigInt::Divide(n1, *n, n0, n2)
      If BigInt::IsZero(n2) : Result = 1 : Break : EndIf
    Next
    ProcedureReturn Result
  EndProcedure
  
  Procedure.i MillerRabin(*n.BigInt::BigInt, k.i)
    ; k is number of iterations, each test reduces the odds by 1/4
    ; 40 is the most you would use. 6 is enough for a 1024 bit number
    ; Returns 0 if composite, 1 if probably prime
    Protected.i Result=1 ; probably prime by default
    Protected.BigInt::BigInt nm1, d
    Protected.BigInt::BigInt n0, n1 ; scratch variables for calculations
    Protected.BigInt::BigInt x
    Protected.i r=0
    Protected.i s=0
    Protected.i Rand_Size    
    BigInt::SetValue(n1, 1)
    BigInt::Assign(nm1, *n)
    BigInt::Subtract(nm1, n1)
    BigInt::Assign(d, nm1)
    While BigInt::GetBit(d, 0)
      BigInt::Shr1(d) : s + 1
    Wend
    OpenCryptRandom()
    While k>0
      k=k-1
      Rand_Size = CryptRandom(BigInt::NumberSize(*n)-2) + 1 ; random number of length between 1 and SizeOf(*n)-1 in bytes
      BigInt::SetValue(n0, 0) : CryptRandomData(n0, Rand_Size)
      BigInt::SetBit(n0, 1) ; set bit so value is at least 2
      BigInt::ModPow(x, n0, d, *n)
      If BigInt::Compare(x, n1)=0 Or BigInt::Compare(x, nm1)=0 : Continue : EndIf  
      For r=1 To s-1
        BigInt::ModMul(x, x, *n) ; x=(x*x)%n
        If BigInt::Compare(x, n1)=0 : Result = 0 : Break 2 : EndIf 
        If BigInt::Compare(x, nm1)=0 : Break : EndIf
      Next
      If BigInt::Compare(x, nm1)<>0 : Result = 0 : Break : EndIf
    Wend
    CloseCryptRandom()
    ProcedureReturn Result
  EndProcedure
  
  Procedure ModInv(*d.BigInt::BigInt, *e.BigInt::BigInt, *p.BigInt::BigInt)
    ; Calculate d=e^-1 mod p
    Protected.BigInt::BigInt d, bal, count, st
    Protected.BigInt::BigInt n0
    Protected.i b1 ; loop condition variable
    BigInt::SetValue(*d, 0)
    BigInt::SetValue(count, 1)
    BigInt::SetValue(bal, 0) : BigInt::Add(bal, *e)
    b1=0
    Repeat
      BigInt::SetValue(st, 0) : BigInt::Add(st, *p) : BigInt::Subtract(st, bal)
      BigInt::Divide(st, st, *e, n0) : BigInt::SetValue(n0, 1) : BigInt::Add(st, n0)
      BigInt::SetValue(n0, 0) : BigInt::Add(n0, st) : BigInt::Multiply(n0, *e) : BigInt::Add(bal, n0)
      BigInt::Add(count, st)
      BigInt::Subtract(bal, *p)
      BigInt::SetValue(n0, 1) : If BigInt::Compare(bal, n0)=0 : b1=1 : EndIf
    Until b1=1
    BigInt::SetValue(*d, 0) : BigInt::Add(*d, count)
  EndProcedure  
  
  Procedure.i GeneratePrime(*n.BigInt::BigInt, l.i)
    ; generates a prime of length l (in bits eg- 512, 1024, 2048)
    ; returns *n
    Protected *RandN
    Protected.i Result = 0 ; failed by default
    Protected.BigInt::BigInt n0
    Protected.i ByteSize = (l >> 3); convert number of bits into a byte size amount (4096 = 256 bytes)
    Protected.i PrimeFound=0       ; loop test
    *RandN = AllocateMemory(ByteSize)
    If *RandN
      OpenCryptRandom()
      CryptRandomData(*RandN, ByteSize)
      CloseCryptRandom()
      BigInt::LoadValue(*n, *RandN, ByteSize, #True)
      ; [0..l..#BigIntBits]
      BigInt::SetBit(*n, 0) ; set the least significant bit to 1
      BigInt::SetBit(*n, l-1) ; set the two most significant bits to 1
      BigInt::SetBit(*n, l-2)
      BigInt::SetValue(n0, 2)
      Repeat
        If Not Composite(*n)
          If MillerRabin(*n, 40)
            PrimeFound=1
          EndIf
        EndIf
        If Not PrimeFound : BigInt::Add(*n, n0): EndIf
      Until PrimeFound
    EndIf
    Result = 1 ; success
    FreeMemory(*RandN)
    ProcedureReturn Result
  EndProcedure
  
  ;- Declared procedures 
  
  Procedure.i GenerateKeyPair (*k.RSAKeyPair, bits.i=2048)
    ; returns 1=success or 0=fail
    ; Common key sizes (as of 2016):
    ; 1024 - slightly outdated
    ; 2048 - presumably secure
    ; 3072 - secure
    ; 4096 - very secure
    ; 5120, 6144, 7168 - future key sizes
    Protected.i Result=0, t1
    Protected.BigInt::BigInt n0, n1, n2, n3
    If bits>=1024 And bits%1024=0
      Debug "Generating " + bits + " bit key pair..."
      *k\KeySize = bits
      BigInt::SetValue(*k\PublicExponent, $010001)
      BigInt::SetValue(n2, 1)
      Repeat
        GeneratePrime(*k\p, bits/2)
        BigInt::Divide(n0, *k\p, *k\PublicExponent, n1)
      Until BigInt::Compare(n1, n2)<>0 ; make sure p mod e doesn't equal 1
      Repeat
        GeneratePrime(*k\q, bits/2)
        BigInt::Divide(n0, *k\q, *k\PublicExponent, n1)
      Until BigInt::Compare(n1, n2)<>0 ; make sure q mod e doesn't equal 1
      BigInt::SetValue(*k\Modulus, 0)
      BigInt::Add(*k\Modulus, *k\p)
      BigInt::Multiply(*k\Modulus, *k\q)
      ; Calculate phi
      BigInt::SetValue(n0, 0) : BigInt::Add(n0,*k\p)
      BigInt::SetValue(n1, 1) : BigInt::Subtract(n0,n1)
      BigInt::SetValue(n2, 0) : BigInt::Add(n2,*k\q)
      BigInt::SetValue(n3, 1) : BigInt::Subtract(n2,n3)
      BigInt::Multiply(n0, n2) : BigInt::SetValue(*k\phi, 0)
      BigInt::Add(*k\phi, n0)
      ; Calculate secret exponent
      ModInv(*k\SecretExponent, *k\PublicExponent, *k\phi)
      Result=1
    Else
      Debug "Bits must be multiple of 1024"
      Result=0
    EndIf
    ProcedureReturn Result
  EndProcedure
  
  Procedure.i RSAProcessRaw (*Output.BigInt::BigInt, *Input.BigInt::BigInt, *K.RSAKeyPair, Key.i = 0)
    ; Processes BigInt numbers without any padding (adds zeros instead of padding)
    ; KeyAction: 0 for public key, 1 for secret (private) key
    ; Returns 0 if unsuccessful, 1 if success
    ; To use BigInt::ModPow() with RSA encryption:
    ; Encrypt:
    ;   BigInt::ModPow(output, input, e, N)
    ; Decrypt:
    ;   BigInt::ModPow(output, encrypted_data, d, N)
    Protected.i Result=0, d0, kp, ks, km
    d0=BigInt::NumberSize(*Input)<<3
    kp=BigInt::NumberSize(*K\PublicExponent)<<3
    ks=BigInt::NumberSize(*K\SecretExponent)<<3
    km=BigInt::NumberSize(*K\Modulus)<<3
    If *K\KeySize>=1024 And *K\KeySize%1024=0 ; check key is a multiple of 1024 or greater
      If d0<=*K\KeySize ; check the data is not too large
        If key = 0 ; use public key
          If kp=24 And km=*K\KeySize ; check public key is present (note: $010001 = 24 bit)
            BigInt::ModPow(*Output, *Input, *K\PublicExponent, *K\Modulus)
            Result=1
          Else
            Debug "Public key invalid"
          EndIf
        Else ; use secret key
          If ks=*K\KeySize And km=*K\KeySize ; check private key is present
            BigInt::ModPow(*Output, *Input, *K\SecretExponent, *K\Modulus)
            Result=1
          Else
            Debug "Secret key invalid"
          EndIf
        EndIf
      Else
        Debug "Input data (" + d0 + " bits) larger than key"
      EndIf
    Else
      Debug "Key size (" + *K\KeySize + " bits) invalid"
    EndIf
    ProcedureReturn Result
  EndProcedure  
  
  Procedure SelfTest()
    Protected.RSAKeyPair K
    Protected.BigInt::BigInt data1, data2 
    Protected.i StartTime, TotalTime
    Debug "Self test"
    StartTime = ElapsedMilliseconds()
    If GenerateKeyPair(K, 2048)
      TotalTime = ElapsedMilliseconds() - StartTime
      Debug("Key generation time: " + Str(TotalTime) + " ms")
      Debug "e: " + BigInt::GetHex(K\PublicExponent)    
      Debug "n: " + BigInt::GetHex(K\Modulus)
      Debug "d: " + BigInt::GetHex(K\SecretExponent)
      BigInt::SetHexValue(data1, "11223344556677889900")
      Debug "Data: " + BigInt::GetHex(data1)
      Debug "Encrypting..."
      StartTime = ElapsedMilliseconds()
      If RSAProcessRaw(data2, data1, K) ; Process data with public key
        TotalTime = ElapsedMilliseconds() - StartTime
        Debug("Total encrypt time: " + Str(TotalTime) + " ms")
        Debug "Encrypted data: " + BigInt::GetHex(data2)
        Debug "Decrypting..."
        StartTime.i = ElapsedMilliseconds()
        If RSAProcessRaw(data1, data2, K, 1) ; use secret key on the data (decrypts the previous RSAProcess)
          TotalTime.i = ElapsedMilliseconds() - StartTime
          Debug "Decrypted data: " + BigInt::GetHex(data1)
          Debug("Total decrypt time: " + Str(TotalTime) + " ms")    
        EndIf
      EndIf
    EndIf
  EndProcedure
  
  CompilerIf #PB_Compiler_IsMainFile
    SelfTest()
  CompilerEndIf
  
  DataSection
  
    PrimeLookup:
    Data.i 3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,   61,   67,   71,   73,
           79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,  139,  149,  151,  157,  163,  167,  173,  179,
           181,  191,  193,  197,  199,  211,  223,  227,  229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,
           293,  307,  311,  313,  317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
           421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,  521,  523,  541,  547,
           557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,  619,  631,  641,  643,  647,  653,  659,  661,
           673,  677,  683,  691,  701,  709,  719,  727,  733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,
           821,  823,  827,  829,  839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
           953,  967,  971,  977,  983,  991,  997,  1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
           1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
           1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
           1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
           1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663,
           1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823,
           1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
           1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
           2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
           2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
           2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
           2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749,
           2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909,
           2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
           3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259,
           3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433,
           3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581,
           3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733,
           3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911,
           3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073,
           4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241,
           4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421,
           4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591,
           4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759,
           4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943,
           4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099,
           5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281,
           5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
           5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641,
           5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801,
           5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953,
           5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143,
           6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311,
           6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481,
           6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679,
           6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841,
           6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001,
           7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211,
           7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417,
           7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573,
           7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727,
           7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927
    
  EndDataSection
  
EndModule

[rmenezes]

Interesting!

Will be following this.

[coco2]

I've uploaded v1.0, a working release, it can now be used to encrypt and decrypt as long as you can provide your own key.

*** module dependencies changed ***

[Keya]

coco2 thankyou very much for your huge number library and RSA module! but what do you use to generate the keys? we can't make use of your fine work if we cant generate keys!
i tried generating a 512bit "vanilla RSA" keypair, but had no luck with it. I dont know if its because your demo uses PKCS or not, but... some help generating the keys would be very much appreciated
Thankyou

Code: Select all

    TestModulus512:
    Data.a  $0D,$55,$3E,$11,$68,$8E,$D2,$9F,$1A,$4B,$E5,$73,$CA,$28,$CD,$1F,
$75,$AA,$02,$FC,$7C,$55,$5E,$0D,$4F,$FB,$9A,$6C,$41,$96,$20,$EA,
$DA,$10,$2D,$04,$C7,$8E,$E0,$21,$7A,$4B,$8A,$81,$E0,$37,$0D,$D9,
$A5,$06,$A6,$5C,$55,$0A,$5A,$15,$D8,$3A,$FD,$BB,$44,$52,$A4,$BA
    TestPrivateKey:
    Data.a $AF,$84,$53,$FE,$2D,$13,$EC,$E0,$8B,$BE,$24,$51,$F9,$F6,$2E,$2F,
$A5,$97,$E7,$81,$05,$31,$5B,$74,$F2,$3A,$3D,$A4,$E1,$50,$70,$63,
$23,$3C,$7A,$E3,$DF,$C8,$75,$87,$CC,$97,$C1,$19,$2B,$29,$1F,$14,
$E0,$E6,$F6,$12,$EA,$6D,$1B,$8D,$91,$9B,$8F,$07,$83,$3D,$2C,$11
    TestPublicKey:
    Data.a $2F,$43,$C1,$00

[coco2]

Hello Keya, thank you I worked hard to try to make a PureBasic RSA algorithm but it was so slow when I finally got it working. When wilbert optimised it with ASM it became so fast but I still don't understand his code. I am working on key generation still, I don't get much time to program lately.

[coco2]

Thanks to some help from wilbert I have finished the key generation function. Just run the module by itself (assuming you also have placed wilbert's bigint module in the same directory) to see key generation demonstrated. 1024 and 2048 are quite fast to generate. 3072 and 4096 bit keys take sometimes up to 30 seconds to generate, because it searches randomly and prime numbers are rarer with these bigger numbers. I may add multi-threading to speed this up. I plan to finish it so there will be a PureBasic implementation of RSA that will compile to all platforms (Windows, Linux and Mac). I still have not tested the keys generated yet I'm just adding a progress update.

EDIT: I have finished testing and added Raw encrypt and decrypt with release 1.4, so as long as you provide your own padding, the module is fully functional Please test performance, it should be as fast as most commercially available packages thanks to wilbert

[Keya]

this is very interesting. great work coco2 and wilbert!!!

[grapy]

3072 and 4096 bit keys take sometimes up to 30 seconds to generate

Hello coco2,
you can make a simple Divide Test against to the first ~1000-3000 prims, before you make
a MillerRabin Test. That makes it much faster to generate random 2048 bit prims.

With 4 threads i have mostly two 2048 bit prims generated in the first 1-5 seconds for the 4096 bit keys.

[coco2]

this is very interesting. great work coco2 and wilbert!!!

Thanks

you can make a simple Divide Test against to the first ~1000-3000 prims, before you make
a MillerRabin Test. That makes it much faster to generate random 2048 bit prims.

With 4 threads i have mostly two 2048 bit prims generated in the first 1-5 seconds for the 4096 bit keys.

I'll have a look at your suggestions thanks grapy

Edit: Thanks very much for your suggestion grapy, I've updated the code now it can generate 4096 bit keys in 2 seconds sometimes !!!

[Keya]

congratulations on the Rabin-Miller!!!

i was just reading how to sign an RSA message https://simple.wikipedia.org/wiki/RSA_% ... g_messages

Suppose Alice wishes to send a signed message to Bob. She produces a hash value of the message, raises it to the power of d mod n (just like when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of e mod n (just like encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with since.

is it possible to implement this? it makes it sound like its based on the existing encryption?

[coco2]

Thanks Keya. Yes you can use RSAProcessRaw to send a signed message as described. Just set Key = 1 to process it using your own private key.

Suppose Alice wishes to send a signed message to Bob. She produces a hash value of the message, raises it to the power of d mod n (just like when decrypting a message)

Use Key = 1 like this:

Code: Select all

RSAProcessRaw(data2, data1, K, 1)

and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of e mod n (just like encrypting a message)

Use Key = 0 like this:

Code: Select all

RSAProcessRaw(data2, data1, K, 0)

[Keya]

lol far out you've made that nice and easy! i thought some new code might've been required but figured from Wiki's signing description that you already had the core in place, so i had to ask!
Encryption + Signing = Supercool!!! Eve can kiss Alice's sweet ass lol

[coco2]

It's simple once you know how to do it. Normally you would encrypt with a public key using key = 0 and decrypt with the private key with key = 1, but for signing you do the reverse, you use the private key to "encrypt" it, and the public key to decrypt.

[Keya]

i guess RSA itself really is simple, but big numbers aren't
awesome we have a couple of big number libraries to choose from as PB'ers!

[coco2]

Wilbert's is really fast, I don't think you can get much faster. Just remember to set bigintbits to 4096 or whatever the highest size you want to use is. It will give strange results if you forget to do it.