RSA Encryption Example

[Booger]

Hello, I couldn't find any example of RSA on these forums. So using PDwer's big math code he posted, I present a slow but working RSA Encryption method.

Posted here to be Optimized by the smart guys.

Dont run with the debugger in use unless you want to wait much longer for a result.

Its way to slow to use my RSA Key Generator code with, so is using the smallest keys my Generator could find in 2 hours.

Code: Select all

;Uses PDwer's Big Math Code on forums.
;RSA implemented by Booger
Structure Bytes
    Byte.b[0]
EndStructure

Declare.s String(Char.s, Length.l)
Declare.l IsBiggerInt(BiggerNum.s, SmallerNum.s )
Declare.s BigDivide(DivThis.s, byThis.s)
Declare.s BigMultiply(Num1.s,Num2.s)
Declare.s BigSubtract(Num1.s, Num2.s) ; Answer = Num1 - Num2 (negative output not handled yet)
Declare.s BigAdd(Num1.s, Num2.s)
Declare.s BigSquared(Num.s)
Declare.s BigPow(Num.s, pow.l)


Procedure.s BigSquared(Num.s)

    carry.l = 0

    Num1Len = Len(num)
    Num2len = Num1Len
   
    AnswerLen = Num1len + Num2len ;+1
   
    Dim BCD1.l(Answerlen)
    Dim BCD2.l(Answerlen)
    Dim BCDA.l(Answerlen)
 
    ;Get Data out of string
    *BytePtr1.Bytes = @Num
    *BytePtr2.Bytes = @Num
   
    For i = 1 To Num1len
        ;bcd1(i) = Val(Mid(Num1,Num1len - i +1 ,1))
        bcd1(i) = *BytePtr1\Byte[Num1len - i] -48
        bcd2(i) = bcd1(i)
    Next
   
    ;multiply
    For L1.l = 1 To Num1len    ;lower number
        carry = 0
        Digit.l = L1;1     
        For L2.l = 1 To Num2len  ;upper number
            BCDA(Digit) + (BCD1(L1) * BCD2(L2)) + carry
            carry = Int(BCDA(Digit) / 10)  ;int()
            BCDA(Digit) = BCDA(Digit) % 10
            Digit + 1   
        Next
                             
        If carry
            BCDA(Digit) = Carry
        EndIf                               
    Next
     
    ; set size
    Answer.s = ""

    For i = AnswerLen To 1 Step -1
        If i = answerlen And bcda(i) = 0
            ;skip trailing 0
        Else
            Answer = Answer + Str(BCDA(i))
        EndIf 
    Next

    ProcedureReturn Answer
   
EndProcedure

Procedure.s BigAdd(Num1.s, Num2.s)

    Carry.b = 0
    Num1Len = Len(num1)
    Num2Len = Len(num2)
    If Num1len > Num2Len
        AnswerLen = Num1len +1
    Else
        AnswerLen = Num2len + 1
    EndIf
   
    Dim BCD1.b(Answerlen)
    Dim BCD2.b(Answerlen)
    Dim BCDA.b(Answerlen)
   
    ;Get Data out of string
   
    For i = 1 To Num1len
        bcd1(i) = Val(Mid(Num1,Num1len - i +1 ,1))
    Next

    For i = 1 To Num2len
        bcd2(i) = Val(Mid(Num2,Num2len - i +1,1))
    Next   
       
    ;add
    For i = 1 To Answerlen   
        BCDA(i) = bcd1(i) + bcd2(i) + Carry
        If BCDA(i) > 9
            BCDA(i) - 10
            carry = 1
        Else
            carry = 0
        EndIf
    Next
   
    Answer.s = ""

    For i = AnswerLen To 1 Step -1
        If i = answerlen And bcda(i) = 0
            ;skip trailing 0
        Else
            Answer = Answer + Str(BCDA(i))
        EndIf
       
    Next
   
    ProcedureReturn Answer
   
EndProcedure

Procedure.s BigSubtract(Num1.s, Num2.s) ; Answer = Num1 - Num2 (negative output not handled yet)

    Carry.b = 0
    Num1Len = Len(num1)
    Num2Len = Len(num2)
    If Num1len > Num2Len
        AnswerLen = Num1len +1
    Else
        AnswerLen = Num2len + 1
    EndIf
   
    Dim BCD1.b(Answerlen)
    Dim BCD2.b(Answerlen)
    Dim BCDA.b(Answerlen)
   
    ;Get Data out of string
   
    For i = 1 To Num1len
        bcd1(i) = Val(Mid(Num1,Num1len - i +1 ,1))
    Next

    For i = 1 To Num2len
        bcd2(i) = Val(Mid(Num2,Num2len - i +1,1))
    Next   
       
    ;add
    For i = 1 To Answerlen   
        BCDA(i) = bcd1(i) - bcd2(i) - Carry
        If BCDA(i) < 0
            BCDA(i) + 10
            carry = 1
        Else
            carry = 0
        EndIf
    Next
   
    Answer.s = ""
   
    StringStart.l = #True

    For i = AnswerLen To 1 Step -1
        If StringStart = #True And bcda(i) = 0  ;If i = answerlen And bcda(i) = 0
            ;skip trailing 0
        Else
            Answer = Answer + Str(BCDA(i))
            StringStart = #False
        EndIf       
    Next   
   
    ProcedureReturn Answer

EndProcedure

Procedure.s BigMultiply(Num1.s,Num2.s)

    carry.l = 0

    Num1Len = Len(num1)
    Num2Len = Len(num2)
   
    AnswerLen = Num1len + Num2len ;+1
   
    Dim BCD1.b(Answerlen)
    Dim BCD2.b(Answerlen)
    Dim BCDA.c(Answerlen)
   
    ;Get Data out of string
    *BytePtr1.Bytes = @Num1
    *BytePtr2.Bytes = @Num2
   
    For i = 1 To Num1len
        bcd1(i) = *BytePtr1\Byte[Num1len - i] -48
    Next

    For i = 1 To Num2len
        bcd2(i) = *BytePtr2\Byte[Num2len - i] -48
    Next

    ;multiply
   
    For L1.l = 1 To Num1len    ;lower number
        carry = 0
        Digit.l = L1;1     
        For L2.l = 1 To Num2len  ;upper number
            BCDA(Digit) + (BCD1(L1) * BCD2(L2)) + carry
            carry = BCDA(Digit) / 10  ;int()
            BCDA(Digit) = BCDA(Digit) % 10
            Digit + 1   
        Next
                             
        If carry
            BCDA(Digit) = Carry
        EndIf                               
    Next
     
    ; set size
   Answer.s = RSet(Chr(0), AnswerLen,Chr(0))

    *AnsPtr.Bytes = @Answer

    For i = AnswerLen To 1 Step -1
        *AnsPtr\byte[AnswerLen - i ] = BCDA(i) + 48
    Next
   
    If Left(Answer,1) = "0"
        Answer = Right(answer,AnswerLen-1)
    EndIf

    ProcedureReturn Answer
   
EndProcedure

Procedure.s BigPow(Num.s, pow.l)

    If pow = 1 ;
        ProcedureReturn num
    ElseIf pow = 2
        ProcedureReturn BigMultiply(Num,num)
    ElseIf pow = 3
        ProcedureReturn BigMultiply(Num, BigPow(Num,2))
    Else
       
       
        If pow % 2 = 0
            ProcedureReturn BigMultiply(BigPow(Num,pow / 2), BigPow(Num,pow / 2)) 
        Else
            ProcedureReturn BigMultiply(BigMultiply(BigPow(Num,pow / 2), BigPow(Num,pow / 2)),num) 
        EndIf
    EndIf
   
EndProcedure

Procedure.l IsBiggerInt(BiggerNum.s, SmallerNum.s ) ;returns true if first int is bigger

    Biglen.l = Len(BiggerNum)
    SmallLen.l = Len(SmallerNum)
   
    If Biglen > SmallLen
        ProcedureReturn #True
    ElseIf Biglen < SmallLen
        ProcedureReturn #False
    Else ;same len, string compare
        If BiggerNum > SmallerNum
            ProcedureReturn #True
        Else
            ProcedureReturn #False
        EndIf       
    EndIf

EndProcedure

Procedure.s BigDivide(DivThis.s, byThis.s)  ; DivThis / byThis (First param should be bigger or result is zero)
   
    Define Result.s , divisorInc.l
   
    DivThislen.l = Len(DivThis)
    byThisLen.l = Len(byThis)
   
    NewDivisor.s = byThis
    NewDivLen.l = byThisLen
   
    If IsBiggerInt(byThis, DivThis)
        ProcedureReturn "0"
    EndIf
   
    DifLen = DivThislen - NewDivLen

    If diflen > 0
   
        divisorInc = Val(Left(DivThis,1)) / Val(Left(byThis,1)) -1
        If divisorInc = < 1
            divisorInc = 1
        EndIf
               
        NewDivisor = BigMultiply(NewDivisor, Str(divisorInc) + string("0",DifLen-1))       
        NewDivLen = Len(NewDivisor)
        Result =  BigAdd(Result, Str(divisorInc) + string("0",DifLen-1))
        ; subtract calced piece
        DivThis = BigSubtract(DivThis, NewDivisor)
        DivThislen = Len(DivThis)
       
        result = bigadd(result,BigDivide(DivThis.s, byThis.s))
    Else
   
        For i = 2 To 10
            If IsBiggerInt(BigMultiply(Str(i),byThis),DivThis)
                result = Str(i-1)
                Break
            EndIf   
        Next
   
    EndIf
   
    ProcedureReturn(result)


EndProcedure

Procedure.s String(Char.s, Length.l)

    If Len(Char) = 1
        TempStr.s = Space(Length)
        ReplaceString(TempStr," ",Char,2)
        ProcedureReturn TempStr
    Else
        ProcedureReturn ""
    EndIf

EndProcedure



; ============= Test code from here ===========

; DisableDebugger
; 
; OpenConsole()
; 
;     Divide.s = "26098234092834075093854092383452340987340295703295702398573290457987043295783240957239032475320948799"
;     By.s     = "9309478523409785234085234095780329457987394752309870987"
; 
;     PrintN("Divide   " + divide)
;     PrintN("By       " + by)
;     PrintN("")
;     PrintN(BigDivide(Divide, by ))
;     Input()
; 
; 
; CloseConsole()

Procedure.s myMod(x.s , y.s )
; '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#
scratch1.s=bigdivide(x,y)
scratch2.s=bigmultiply(scratch1,y)
z.s = bigsubtract(x,scratch2)
ProcedureReturn z
EndProcedure

Procedure.s encrypt(character.d, key1.d, key2.d,dec=0)
;Debug character
;Debug key2
;Debug key1
PrintN("Doing BigPow function now...")
b.s=BigPow(Str(character), key2)
PrintN(b)
PrintN("Doing MyMod function now...")
  c.s =mymod(b,Str(key1))
  PrintN(Chr(Val(c)))
  ;Debug Hex(c)
  ;Debug Chr(123)
  If dec=0
  ProcedureReturn RSet(Hex(Val(c)),8,"0")
  Else
  ProcedureReturn Chr(Val(c))
  EndIf
EndProcedure
Global e.d = 3;private key
Global d.d = 187;public key
Global n.d = 319;public key

Global text$ = "Hello"
OpenConsole()
For x = 1 To Len(text$)
  character = Asc(Mid(text$, x, 1))
  result.s + encrypt(character, n, e)
Next
PrintN("Encrypted!!!")
PrintN(text$+"="+result)

For x=1 To Len(result) Step 8
CharacterReverse.s="$"+Mid(result,x,8)
character=Val(characterReverse)
result2.s+encrypt(character, n, d,1)
Next
PrintN("Decrypted!!!")
PrintN(result+"="+result2)
Input()

[Booger]

New Much Faster Version. This one is close to practical. Can Use much larger Key pairs.

Code: Select all

;BASIC RSA
;By Booger


Procedure.s encrypt(character.q, key1.q, key2.q, dec = 0)
  ;*********************************************************
  ;Modular exponentiation
  ;Memory-efficient method
  ee.q = 0
  b.q = character
  cc.q = 1
  e.q = key1
  m.q = key2
  While ee<e
    ee + 1
    cc = (b*cc)%m
  Wend
  ;*********************************************************
  c.s = Str(cc)
  If dec = 0
    ProcedureReturn RSet(Hex(Val(c)), 8, "0")
  Else
    ProcedureReturn Chr(Val(c))
  EndIf
EndProcedure
timer = ElapsedMilliseconds()
e.d = 17;private key
d.d = 2753;public key
n.d = 3233;public key

text$ = "Hello, how are you today? Test Encryption"
OpenConsole()
For x = 1 To Len(text$)
  character = Asc(Mid(text$, x, 1))
  result.s + encrypt(character, e, n)
Next
PrintN("Encrypted!!!")
PrintN(text$ + "=" + result)

For x = 1 To Len(result) Step 8
  CharacterReverse.s = "$" + Mid(result, x, 8)
  character = Val(characterReverse)
  result2.s + encrypt(character, d, n, 1);set dec flag on decryption, otherwise you get hex back
Next
PrintN("Decrypted!!!")
PrintN(result + "=" + result2)
PrintN("time taken was " + StrF((ElapsedMilliseconds()-timer)/1000) + " Seconds")
Input()

Example encryption with two 64bit pairs.

Code: Select all

Hello, how are you today? Test Encryption=01042E0C01D605F102A0661202A0661201CDF9
97018A564A00FD197802C9B29E01CDF99701E2D7D900FD1978017BA14900C0435001D605F100FD19
7800C0EB0901CDF99701C90FFB00FD19780329E45401CDF99701D3AD00017BA14900C0EB09023C2A
0D00FD197801F50C2401D605F1014C5BBB0329E45400FD197800A62FAB0103B6A4009F037500C043
5000C0EB09027FBDA00329E45402C9414D01CDF9970103B6A4

[DoubleDutch]

Thanks for the routine.

But, the example ouput you show doesn't seem to match the output of the program shown - they seem to be extended to 8 character hex digits.

Also, could you show me info on how to generate these values:
e.d = 17;private key <-- is this not really the public key exponent?
d.d = 2753;public key <--- is this not really the private key exponent?
n.d = 3233;public key

have you written a routine to calculate the values from p and q (the 64 bit pairs)?

[Booger]

I hypothesize the example code is 16 bit keys from the wikipedia explanation of how RSA works. The output shown is from two 64 bit keys with higher math routines than what is in the example. This routine as it is can do 32 bit keys.

And yes I have written the routine to calculate keys. Although it uses my higher math routine Library which is not in a release stage.

The Public and Private keys may be reversed with no quirks as far as I can tell, either way it still works. As such they may be labeled incorrectly.

You are correct in the assumption that each character is indeed converted to a 8 character hex. RSA deals with very large numbers. Prime math is indeed mindbogglingly goofy.

I have high speed calculation now if interested.

Code: Select all

;BASIC RSA
;By Booger


Procedure.s encrypt(character.q, key1.q, key2.q, dec = 0)
  ;*********************************************************
  ;Modular exponentiation
  ;Memory-efficient method
  ee.q = 0
  b.q = character
  cc.q = 1
  e.q = key1
  m.q = key2
;   While ee<e
;     ee + 1
;     cc = (b*cc)%m
;   Wend
  ;*********************************************************
  ;Right-to-left binary method
  ;binary exponentiation
  While e>0
    If e&1=1
    cc=(cc*b)%m
    EndIf
    e>>1
    b=(b*b)%m
    Wend
    
  c.s = Str(cc)
  If dec = 0
    ProcedureReturn RSet(Hex(Val(c)), 8, "0")
  Else
    ProcedureReturn Chr(Val(c))
  EndIf
EndProcedure
timer = ElapsedMilliseconds()
; e.d = 1105413601;private key
; d.d = 32789473;public key
; n.d = 37941461;public key
;calculating primes for P...
;Found prime for P...39227
;calculating primes for Q...
;Found prime for Q...43151
;Calculating E and D...
E.q=717229451
D.q=173322251
N.q=1692684277












text$ = "Hello, how are you today? Test Encryption"
OpenConsole()
For x = 1 To Len(text$)
  character = Asc(Mid(text$, x, 1))
  result.s + encrypt(character, e, n)
Next
PrintN("Encrypted!!!")
PrintN(text$ + "=" + result)

For x = 1 To Len(result) Step 8
  CharacterReverse.s = "$" + Mid(result, x, 8)
  character = Val(characterReverse)
  result2.s + encrypt(character, d, n, 1);set dec flag on decryption, otherwise you get hex back
Next
PrintN("Decrypted!!!")
PrintN(result + "=" + result2)
PrintN("time taken was " + StrF((ElapsedMilliseconds()-timer)/1000) + " Seconds")
Input()

[DoubleDutch]

Ahh, I saw the Wikipedia entry as well - you used the same variable names as in the example.

Although it uses my higher math routine Library which is not in a release stage.

Are you going to release this? If so, a good example would be your routines to generate the large primes.

[Booger]

Yes, it is planned to be released when it is proven accurate.

See General Discussion thread here:

http://www.purebasic.fr/english/viewtopic.php?t=37186


Thanks.

[NoahPhense]

What ever happened to this? Sort of useless without knowing an algorithm for the public and private keys.

- np

[Booger]

Generating the keys can take hours. And as such is open to ridicule. As most dont understand why, plus the unknown legality of such code to generate keys, my advisor has advised not to release that type of code. Sorry.

[NoahPhense]

It's all good. I wrote my own algorithm, which laughs at RSA enc/dec, posted it as a "crack me" to the users of the language that I was using at that time, I offered $10K to someone to reverse engineer the output. Haven't heard anything yet. So, yes, I do understand anonymity.

- np

[Joakim Christiansen]

It's all good. I wrote my own algorithm, which laughs at RSA enc/dec

You mean to say you laugh at RSA because you can make a "better" algorithm?

I too can write fairly hard to reverse engineer encryption, but I wouldn't laugh at other algorithms or even think that my algorithm is anywhere close to as safe. There sure are some highly skilled math geeks who have made the popular algorithms and neither you or me can compare us with them at all. :roll:

[NoahPhense]

It's all good. I wrote my own algorithm, which laughs at RSA enc/dec

You mean to say you laugh at RSA because you can make a "better" algorithm?

I too can write fairly hard to reverse engineer encryption, but I wouldn't laugh at other algorithms or even think that my algorithm is anywhere close to as safe. There sure are some highly skilled math geeks who have made the popular algorithms and neither you or me can compare us with them at all. :roll:

Agreed. But never saw a $10k reward for reversing RSA yet?

- np