2017-12-15

Navigation

Skip Navigation Links

Hash algorithms

Asymmetric Algorithms

Symmetric Cipher Algorithms

Encoding Algorithms

Compression Algorithms

Pseudo Random Number Algorithms

Steganography

Library Wrappers

String Comparison

Others

Syntax highlighting by Prism
PBCrypto.com Mirror

RSA 64-bit

Algorithm creator(s)

Ronald Rivest, Adi Shamir, Leonard Adleman


PB author(s)

Wayne Diamond


Description

The worlds first (publically disclosed) secure public key exchange system.


Note

The honour of finding an asymmetric cipher fell to James Ellis and Clifford Cocks of the British GCHQ in 1973. Sadly, due to the secrecy of their work they had to remain silent and watch while their discoveries were rediscovered 4 years later by Diffie, Hellman, Merkle, Rivest, Shamir and Adleman over the next three years. For stronger RSA we need a good PB big number library! *hint*


Source

https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/23952-64-bit-rsa-public-key-cryptography-comes-to-pb?t=23327


See also

n/a


Source Code

Download source code file rsa64.bas (Right-click -> "Save as ...")

#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 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

 
'/////////////////////////////////////////////////////
'// 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

Mirror provided by Knuth Konrad