Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

64-bit RSA! Public key cryptography comes to PB

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

  • 64-bit RSA! Public key cryptography comes to PB

    i think this is the only rsa source available so far for pb. don dickinson has posted a nice demo that demonstrates how to use microsoft's rsa base cryptographic service, but this demo provides the actual encryption/decryption sources itself, not relying on any 3rd party components.
    don dickinsons sample can be found at and is recommended reading

    this is a 'direct' port from vb to pb. i used an rsa sample that i downloaded sometime last year, probably from planetsourcecode or somewhere similar, but wasn't able to find exactly where i got it from. however, i do know that the author's name is w.g. griffiths, and he is the person to thank for making this possible -- it only took me half an hour to port, and porting can't really be considered 'work'
    this is <u>not optimised!</u> in fact its probably as unoptimised as you could get due to porting it from vb, but it works well and could easily be converted to fast inline assembly.
    anyway, enjoy!

    Code:
    #compile exe
    #include "win32api.inc"
      
    global key() as double
    global p as double, q as double
    global phi as double
     
    declare function dec(tip as string, dd as double, dn as double) as string
    declare function enc(tip as string, ee as double, en as double) as string
    declare function nmod(x as double, y as double) as double
    declare function mult(byval x as double, byval p as double, byval m as double) as double
    declare function isprime(lngnumber as double) as byte
    declare function gcd(nphi as double) as double
    declare function euler(e3 as double, phi3 as double) as double
    declare sub keygen()
     
    sub keygen()
    'generates the keys for e, d and n
    dim e#, d#, n#
    %pq_up = 9999 'set upper limit of random number
    %pq_lw = 3170 'set lower limit of random number
    %key_lower_limit = 10000000 'set for 64bit minimum
    p = 0: q = 0
    randomize timer
    do until d > %key_lower_limit 'makes sure keys are 64bit minimum
    do until isprime(p) and isprime(q) ' make sure q and q are primes
    p = int((%pq_up - %pq_lw + 1) * rnd + %pq_lw)
    q = int((%pq_up - %pq_lw + 1) * rnd + %pq_lw)
    loop
        n = p * q
        phi = (p - 1) * (q - 1)
        e = gcd(phi)
        d = euler(e, phi)
    loop
            key(1) = e
            key(2) = d
            key(3) = n
    end sub
     
    function euler(e3 as double, phi3 as double) as double
    'genetates d from (e and phi) using the euler algorithm
    on error resume next
    dim u1#, u2#, u3#, v1#, v2#, v3#, q#
    dim t1#, t2#, t3#, z#, uu#, vv#, inverse#
    u1 = 1
    u2 = 0
    u3 = phi3
    v1 = 0
    v2 = 1
    v3 = e3
    do until (v3 = 0)
         q = int(u3 / v3)
         t1 = u1 - q * v1
         t2 = u2 - q * v2
         t3 = u3 - q * v3
         u1 = v1
         u2 = v2
         u3 = v3
         v1 = t1
         v2 = t2
         v3 = t3
         z = 1
    loop
    uu = u1
    vv = u2
    if (vv < 0) then
              inverse = vv + phi3
    else
         inverse = vv
    end if
    euler = inverse
    end function
     
    function gcd(nphi as double) as double
    'generates a random number relatively prime to phi
    on error resume next
    dim ne#, y#
    dim x as double
    %n_up = 99999999 'set upper limit of random number for e
    %n_lw = 10000000 'set lower limit of random number for e
    randomize
    ne = int((%n_up - %n_lw + 1) * rnd + %n_lw)
    top:
        x = nphi mod ne
        y = x mod ne
        if y <> 0 and isprime(ne) then
            gcd = ne
            exit function
        else
            ne = ne + 1
        end if
        goto top
    end function
     
    function isprime(lngnumber as double) as byte
    'returns '%true' if lngnumber is a prime
    on error resume next
    dim lngcount#
    dim lngsqr#
    dim x#
    lngsqr = int(sqr(lngnumber)) ' get the int square root
        if lngnumber < 2 then
            isprime = %false
            exit function
        end if
        lngcount = 2
        isprime = %true
        if lngnumber mod lngcount = 0 then
            isprime = %false
            exit function
        end if
        lngcount = 3
        for x = lngcount to lngsqr step 2
            if lngnumber mod x = 0 then
                isprime = %false
                exit function
            end if
        next
    end function
     
    function mult(byval x as double, byval p as double, byval m as double) as double
    dim y as double
    'encrypts, decrypts values passed to the function.. e.g.
    'mult = m^e mod n (encrypt)  where m = x , e = p, n = m
    'mult = m^d mod n (decrypt)
    on error goto error1
    y = 1
        do while p > 0
            do while (p / 2) = int((p / 2))
                x = nmod((x * x), m)
                p = p / 2
            loop
            y = nmod((x * y), m)
            p = p - 1
        loop
        mult = y
        exit function
    error1:
    y = 0
    end function
     
    function nmod(x as double, y as double) as double
    'this function replaces the mod command. instead of z = x mod y
    'it is now  z = nmod(x,y)
    on error resume next
    dim z#
    z = x - (int(x / y) * y)
    nmod = z
    end function
     
    function enc(tip as string, ee as double, en as double) as string
    'returns the long value of the characters, chained with a +
    'e.g. 12345678+23456789+ etc..
    '**taken out encryption algorithm to simplify program**
    on error resume next
    dim encst as string
    dim e2st as string
    dim i as long
    encst = "
    e2st = "
        if tip = " then exit function
        for i = 1 to len(tip)
            encst = encst & trim$(str$(mult(clng(asc(mid$(tip, i, 1))), ee, en)) & "+")
        next i
    '** put your encryption algorithm code here **
    enc = encst
    end function
     
    function dec(tip as string, dd as double, dn as double) as string
    'returns the characters from the long values
    'e.g a = 12345678, b = 23456789 etc..
    '**taken out decryption algorithm to simplify program**
    on error resume next
    dim decst as string
    dim z as long
    dim zptr as long
    dim tok as long
    decst = "
    '** put your decryption algorithm code here **
    for z = 1 to len(tip)
        zptr = instr(z, tip, "+")
        tok = val(mid$(tip, z, zptr))
        decst = decst + chr$(mult(tok, dd, dn))
        z = zptr
    next z
    dec = decst
    end function
     
    '/////////////////////////////////////////////////////
    '// demo program - creates private and public keys, //
    '// then encrypts and decrypts a test string.       //
    '/////////////////////////////////////////////////////
    function pbmain() as long
    redim key(3) as double
    dim encstr as string
    dim decstr as string
    dim plaintext as string
    plaintext = "abcdefghijklmnopqrstuvwxyz 1234567890"   'the message to encrypt
    keygen
    stdout "result:"
    stdout " p=" & str$(p)
    stdout " q=" & str$(q)
    stdout " phi=" & str$(phi)
    stdout " e=" & left$(str$(key(1)) & space$(12),12) & "private key"
    stdout " d=" & left$(str$(key(2)) & space$(12),12) & "public key"
    stdout " n=" & left$(str$(key(3)) & space$(12),12) & "public key"
    stdout
    stdout "plaintext: " & plaintext
    encstr = enc(plaintext, key(1), key(3))
    stdout "encrypted: " & encstr
    decstr = dec(encstr, key(2), key(3))
    stdout "decrypted: " & decstr
    waitkey$
    end function
    ------------------
    -

  • #2
    NB. Obviously the above source is for PBCC, but you can easily get it going in PBDLL by changing STDOUT to MSGBOX, and deleting the WAITKEY$ statement.
    Also, 64-bit is not very strong (it's not WEAK, but it's not bulletproof) -- always look for at least 128-bit for really strong security.

    Here is the descriptive text that accompanied the source:
    How RSA Works
    =============
    We begin with choosing two random large distinct primes p and q. We
    also pick e, a random integer that is relatively prime to (p-1)*(q-1). The
    random integer e is the encryption exponent. Let n = p*q. Using Euclid's
    greatest common divisor algorithm, one can compute d, the decryption
    exponent, such that:
    e*d = 1 (mod (p-1)*(q-1))
    Both plaintext m and ciphertext c should be in the set of nonnegative
    integers. Furthermore, before encrypting a plaintext message m, we need
    to make sure that 0 <= m < n. If m is greater than the modulus n, the result
    c of the encryption will not be a unique one-to-one mapping from m to c.
    From one of the theorems of Euler's, we know that for all integers m,
    med = m (mod n)
    Therefore, provided that 0 <= m < n,
    med (mod n) = m
    To encrypt a message m, we perform the following algorithm:
    Ek(m) = me (mod n) = c
    where Ek( ) denotes the encryption algorithm.
    To decipher the ciphertext c with the private key d, we perform the
    following algorithm:
    Dk(c) = cd (mod n) = med (mod n) = m1 (mod n) = m
    where Dk( ) denotes the decryption algorithm.
    The pair (e, n) make up the public-key of the RSA Cryptosystem.
    Everyone can use the pair (e, n) to encrypt a message. For example, Alice
    can publish her (e, n) public-key pair on the network. When Bob wants to
    send a secret message to Alice, he finds Alice's public-key set (e, n) from
    the network and encrypts his message using Alice's public-key: c = me
    (mod n).
    p, q, and d make up Alice's private-key. Only Alice knows p, q, and d. A
    third party, Carol, cannot understand what Bob wrote Alice because Carol
    does not have the private-key. When Alice gets the message from Bob,
    she decrypts it using her private-key set d, n by performing cd (mod n) =
    m.
    Without knowing d, one cannot decrypt the ciphertext c and get message
    m back. To get d, one needs to know (p-1)*(q-1) in order to find d from the
    equation e*d = 1 (mod (p-1)*(q-1)). Furthermore, to get (p-1)*(q-1), one
    needs to first be able to factor the large number n into its primes p and q.
    Since all the numbers involved are very large numbers, we can say that it
    is essentially computationally impossible for an illegitimate party to obtain d,
    and thus decrypt the ciphertext.

    · RSA Example

    Given p = 29, q = 31, e = 13, m = 123;

    ==>We compute: n = p * q = 899
    (p-1)*(q-1) = 840
    d = 517 since e*d = 13*517 = 8*(p-1)*(q-1) + 1
    To encrypt,
    c = 123^13 (mod 899) = 402
    And to decrypt,
    m = 402^517 (mod 899) = 123


    ------------------
    -

    Comment


    • #3
      I've enhanced the encrypt and decrypt functions so that rather than having each character encrypted to 8-9 bytes (eg. "a" might encrypt to become "3042913+"), each encrypted character is now only 4 bytes in size.

      Its simple - it pads the number with 0's on the left to ensure that it's 8 characters, eg. "03042913". That is then broken into 4 bytes, eg 03, 04, 29, 13. Before decrypting, it simply turns 03, 04, 29, 13 back into "3042913" which it can then decrypt back to "a" -- too easy!

      Simply replace the enc and dec functions with these three functions:

      Code:
      FUNCTION GoHex(xLng AS LONG) AS STRING
      ON ERROR RESUME NEXT
      DIM I AS LONG
      DIM xStr AS STRING
      DIM OutStr$
      xStr = RIGHT$("00000000" & TRIM$(STR$(xLng)), 8)
      FOR I = 1 TO LEN(xStr)
       OutStr$ = OutStr$ & CHR$(VAL("&h" & MID$(xStr, I, 2)))
       ! inc I
      NEXT I
      FUNCTION = OutStr$
      END FUNCTION
       
      FUNCTION enc(tIp AS STRING, eE AS DOUBLE, eN AS DOUBLE) AS STRING
      ON ERROR RESUME NEXT
      DIM encSt AS STRING
      DIM e2st AS STRING
      DIM I AS LONG
      encSt = ""
      e2st = ""
      IF tIp = "" THEN EXIT FUNCTION
      FOR i = 1 TO LEN(tIp)
          encSt = encSt & GoHex(Mult(CLNG(ASC(MID$(tIp, i, 1))), eE, eN))
      NEXT i
      enc = encSt
      END FUNCTION
       
      FUNCTION dec(tIp AS STRING, dD AS DOUBLE, dN AS DOUBLE) AS STRING
      ON ERROR RESUME NEXT
      DIM decSt AS STRING
      DIM z AS LONG
      DIM zptr AS LONG
      DIM sTmp AS STRING
      DIM tok AS LONG
      decSt = ""
      FOR z = 1 TO LEN(tIp)
          sTmp = sTmp & HEX$(ASC(MID$(tIp,z,1)),2)
          sTmp = sTmp & HEX$(ASC(MID$(tIp,z+1,1)),2)
          sTmp = sTmp & HEX$(ASC(MID$(tIp,z+2,1)),2)
          sTmp = sTmp & HEX$(ASC(MID$(tIp,z+3,1)),2)
          tok = VAL(sTmp)
          decSt = decSt + CHR$(Mult(tok, dD, dN))
          ! add z, 3
          sTmp = ""
      NEXT z
      dec = decSt
      END FUNCTION
      ------------------
      -

      Comment

      Working...
      X