Jump to content

Toy RSA Encryption Example - Simple concepts for learning Public Key Encryption

Recommended Posts

I found this article and enjoyed it so much I had play with some code since the numbers are small enough. 



Standard Encryption's vs RSA Encryption (Public Key Encryption) Fundamental Differences
If you read that and couldn't immediately clarify the difference then let me blow your mind because its simple:


ORIGINAL_DATA + Password(or KEY) = Encrypted DATA
    Then to decrypt -> 
        Encrypted DATA + (SAME Password(or SAME KEY)) = ORIGINAL_DATA
        ORIGINAL_DATA + Password(or PUBLIC_KEY) = Encrypted DATA
    Then to decrypt -> 
        Encrypted DATA + (DIFFERENT Password(or PRIVATE_KEY)) = ORIGINAL_DATA

Are we all caught up? Did the colors help? I think they did :)

That's crazy right? Don't answer. It is. And crazier its used EVERY TIME we make a secure connection to a server over the internet. But here's the craziest part to me that I recently got clarity on from the toy example and that is the simplicity of this very very very very important algorithm that has yet to be cracked (fingers crossed):

           Mod($vData ^ $key, $n)
So ya. That's it. That's the magic algorithm. 3 values. Oh and $n is also a shared known value that will be in the certificate with the public key that your browser reads when it makes a connection:


That's just mind blowing to me so couldn't resist getting something going in AUT. After playing with this code, I got a much better understanding of how its not just that algorithm that makes this whole thing possible. The numbers that we pick to form the public key and n are just as important and also how important it is to be random! 

Let me know if you have any problems. Enjoy!

#include <array.au3>


Func _Toy_RSA_Example()

    Local $p, $q, $n, $nT, $e, $d
    Local $aPublicKeys, $aCrypt, $sDecrypt, $sMsg

    ;Pick two random primes (they will be between 1000-10000)
    $p = _GetRandomPrime()
    $q = _GetRandomPrime()
    $sMsg = 'p=   %i \t\t|  Prime 1  - [NOT SHARED!]\nq=   %i \t\t|  Prime 2  - [NOT SHARED!]\n'

    ;Calculate lowest common multiple
    $nT = _LCM($p - 1, $q - 1)
    $sMsg &= 'nT= %i \t|  _LCM(p - 1,q - 1) - [NOT SHARED!]\n'

    ;Calculate n. This is a shared number
    $n = $p * $q
    $sMsg &= 'n=   %i \t|  p * q - [Shared]\n'

    ;Get a small random list of possible public keys to pick from. Only searching for 100ms
    $aPublicKeys = _GetPublicKeys($nT)
    _ArrayDisplay($aPublicKeys, "Possible Public Keys Found")

    ;Pick a random public (encryption) key from array
    $e = $aPublicKeys[Random(1, $aPublicKeys[0], 1)]
    $sMsg &= 'e=   %i \t|  Public (Encryption) Key - [Shared]\n'

    ;Generate our private (decryption) key
    $d = _GetPrivateKey($e, $nT)
    $sMsg &= 'd=   %i \t|  Private (Decryption) Key - [NOT SHARED!]\n'

    ;format our msg (rsa details) to encrypt
    $sMsg = StringFormat($sMsg, $p, $q, $nT, $n, $e, $d)

    ;encrypt message
    $aCrypt = _RSA($sMsg, $e, $n)
    _ArrayDisplay($aCrypt, 'Encrypted RSA messsage')

    ;Decrypt array back
    $sDecrypt = _RSA($aCrypt, $d, $n)
    MsgBox(0, 'Decrypted RSA messsage', $sDecrypt)

EndFunc   ;==>_Toy_RSA_Example

;Function will perfrom Mod($v ^ $key, $n) on each char/element.
;Excepts Arrays or Strings. If input is array a string is returned and vice versa.
Func _RSA($vDat, $key, $n)
    Local $bIsStr = IsString($vDat)
    If $bIsStr Then $vDat = StringToASCIIArray($vDat)
    For $i = 0 To UBound($vDat) - 1
        $vDat[$i] = _Modular($vDat[$i], $key, $n)
    Return $bIsStr ? $vDat : StringFromASCIIArray($vDat)
EndFunc   ;==>_RSA

;algorithm is from the book "Discrete Mathematics and Its Applications 5th Edition" by Kenneth H. Rosen.
Func _Modular($iBase, $iExp, $iMod) ;  Mod($v ^ $key, $n)
    Local $iPower = Mod($iBase, $iMod)
    Local $x = 1

    For $i = 0 To (4 * 8) - 1
        If BitAND(0x00000001, BitShift($iExp, $i)) Then
            $x = Mod(($x * $iPower), $iMod)
        $iPower = Mod(($iPower * $iPower), $iMod)

    Return $x
EndFunc   ;==>_Modular

;Generate a "random" list of possible valid public keys to choose from based on $nT
Func _GetPublicKeys($nT, $iMs = 100)
        Local $aKeys[10000] = [0], $iTime = TimerInit()
        Local $i = (Mod(@SEC, 2) ? Int($nT / 2) : Int($nT / 4)) ; randomize where we start
            If _IsPrime($i) And _IsCoPrime($i, $nT) Then
                $aKeys[0] += 1
                $aKeys[$aKeys[0]] = $i
            $i += (Mod(@MSEC, 2) ? 1 : 100) ; randomize step size
        Until ($i >= ($nT - 1)) Or (TimerDiff($iTime) > $iMs)
        ReDim $aKeys[$aKeys[0] + 1]
    Until $aKeys[0] > 5 ; Ive seen 200+ returned sometimes and 0 on others. Make sure we have at least a few choices
    Return $aKeys
EndFunc   ;==>_GetPublicKeys

;https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/  - _ModInverse(a,m)
Func _GetPrivateKey($a, $m)
    If ($m = 1) Then Return 0 ;

    Local $t, $q, $y = 0, $x = 1, $m0 = $m
    While ($a > 1)
        $q = Int($a / $m) ;q is quotient
        $t = $m ;

        $m = Mod($a, $m) ;m is remainder now, process same as Euclid's algo
        $a = $t ;
        $t = $y ;

        $y = $x - $q * $y ;Update y and x
        $x = $t ;

    Return $x < 0 ? $x + $m0 : $x
EndFunc   ;==>_GetPrivateKey

;Pick the next nearest prime from a random number (or number you cho0se)
Func _GetRandomPrime($iStart = Default)
    Local $iPrime = ($iStart = Default ? Random(1000, 10000, 1) : $iStart)
        $iPrime += 1
    Until _IsPrime($iPrime)
    Return $iPrime
EndFunc   ;==>_GetRandomPrime

#Region Math Functions

Func _IsPrime($n)
    For $i = 2 To (Int($n ^ 0.5) + 1)
        If Mod($n, $i) = 0 Then Return False
    Return True
EndFunc   ;==>_IsPrime

Func _IsCoPrime($a, $b)
    Return _GCD($a, $b) = 1
EndFunc   ;==>_IsCoPrime

Func _GCD($iX, $iY)
    Local $iM
    While 1
        $iM = Mod($iX, $iY)
        If $iM = 0 Then Return $iY
        $iX = $iY
        $iY = $iM
EndFunc   ;==>_GCD

Func _LCM($iX, $iY)
    Return ($iX * $iY) / _GCD($iX, $iY)
EndFunc   ;==>_LCM

#EndRegion Math Functions


You should get a message box displaying the decrypted message with details of the values used:




Edited by Beege
Link to post
Share on other sites

For those who are interestd in go a little bit deeper, I think Khan academy has done a topic (with videos) about it, that is where I learned about how RSA works and how it was independently rediscovered.

A little bit of math logic and prime numbers you can have a good way to encrypt data without a single shared key. Asymmetrical encryption they call it I think :)


I found the topic: Journey into cryptography, it covers RSA in the modern cryptography section: https://www.khanacademy.org/computing/computer-science/cryptography#modern-crypt

EasyCodeIt - A cross-platform AutoIt implementation

DcodingTheWeb Forum - Follow for updates and Join for discussion

Link to post
Share on other sites
5 minutes ago, TheDcoder said:

I found the topic: Journey into cryptography, it covers RSA in the modern cryptography section: https://www.khanacademy.org/computing/computer-science/cryptography#modern-crypt

Nice thank you! I love a lot of topics on that page :D 

Link to post
Share on other sites

For those who would want to experiment with larger numbers (not too large though) you can use the _BigNum_PowerMod function I've posted somewhere.

Here it is, with a BigNum prime test (good enough for experimentation but unsuitable for military grade application):

Function names should be instead _BigNum_PowerMod (only one leading _) and _BigNum_IsComposite for consistancy.

_BigNum_GCD() and _BigNum_LCM() left as a trivial exercise.

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Recently Browsing   0 members

    No registered users viewing this page.

  • Similar Content

    • By RTFC
      CodeCrypter enables you to encrypt scripts without placing the key inside the script.
      This is because this key is extracted from the user environment at runtime by, for example:
      password user query any macro (e.g., @username) any AutoIt function call any UDF call some permanent environment variable on a specific machine (and not created by your script) a server response a device response anything else you can think of, as long as it's not stored in the script any combination of the above You need several scripts to get this to work, and they are scattered over several threads, so here's a single bundle that contains them all (including a patched version of Ward's AES.au3; with many thanks to Ward for allowing me to include this script here):
      Latest version: 3.4 (3 Dec 2021): please follow this link.
      Note: if you experience issues under Win8/8.1 (as some users have reported), please upgrade to Win10 (or use Win7) if you can; as far as I can tell, the scripts in the bundle all work under Win7 & Win10 (and XP). Moreover, I have no access to a Win8 box, so these issues will not be fixed, at least not by yours truly.
      How the bits and pieces fit together:
      CodeCrypter is a front-end for the MCF UDF library (you need version 1.3 or later). Its thread is here:
      '?do=embed' frameborder='0' data-embedContent>>
      The MCF package (also contained in the CodeScannerCrypter bundle) contains MCF.au3 (the library itself) plus a little include file called MCFinclude.au3. The latter you have to include in any script you wish to encrypt. Any code preceding it will not be encrypted, any code following it will be encrypted. You define the dynamic key inside MCFinclude.au3, in the UDF: _MCFCC_Init().
      From the same post you can download an MCF Tutorial which I heartily recommend, because encrypting a script requires a number of steps in the right order, namely:
      In MCFinclude.au3, define and/or choose your dynamic key(s) (skip this step = use default setting) include MCFinclude.au3 in your target script Run CodeScanner (version 2.3+) on your target script, with setting WriteMetaCode=True (see '?do=embed' frameborder='0' data-embedContent>>), then close CodeScanner. Start CodeCrypter press the Source button to load your target file enable Write MCF0 (tick the first option in Main Settings) Enable "Encrypt" (last option in the Main Settings) Go to the Tab Encrypt and set up the encryption the way you want (skip this = use default settings) Return to Main Tab and press "Run" if all goes well, a new script called MCF0test.au3 is created in the same directory as your target. It has no includes and no redundant parts. Please check that it works as normal. (see Remarks if not) It all sounds far more complicated than it is, really.
      Not convinced? Check out:
      a simple HowTo Guide: HowToCodeCrypt.pdf an updated and extended Q & A pdf (FAQ, also included in the bundle) to help you get started:CodeCrypterFAQ.pdf For additional explanations/examples in response to specific questions by forum members (how it works, what it can/cannot do), see elsewhere in this thread, notably:
      Simple analogy of how it works: post #53, second part General Explanation and HowTo: post #9, 51, 75, 185/187, 196, 207, 270, 280 (this gets a bit repetitive) BackTranslation: post #179 Obfuscation: post #36 (general), 49 (selective obfuscation) Specific features and fixes: post #3 (security), 84 (redefining the expected runtime response), 169 (Curl Enum fix), 185/187 (using license keys), 194 (replacing Ward's AES UDF with different encryption/decryption calls), 251 (AV detection issue), 262 (extract key contents to USB on different target machine prior to encryption) Limitations: post #26 (@error/@extended), 149 (FileInstall), 191 (AES.au3 on x64) Not recommended: post #46/249 (static encryption), 102 (programme logic error), 237 (parsing password via cmdline)  
      Technical notes:
      BackTranslation is a test to check that the MetaCode translation worked. Skip it at your peril. It also turns your multi-include composite script into a single portable file without redundant parts (you can opt to leave the redundant parts in, if you want).
      CodeCrypter can also obfuscate (vars and UDF names) and replace strings, variable names and UDF names with anything else you provide, for  example, for language translation). After CodeScanner separates your target's structure from its contents, CodeCrypter (actually MCF, under the hood) can change any part, and then generate a new script from whichever pieces you define. See the MCF Tutorial for more explanation and examples.
      Encryption currently relies on Ward's excellent AES UDF and TheXman's sophisticated CryptoNG bundle. You can replace these with any other algorithm you like (but this is not trivial to do: edit MCFinclude.au3 UDF _MCFCC(), and MCF.au3 UDF _EncryptEntry(), see post #194 in this thread). AES by Ward, and CryptoNG by TheXman are also included in the bundle (with many thanks to Ward and TheXman for graciously allowing me to republish their outstanding work).
      Going to lie down now...
    • By RTFC
      The CodeScannerCrypterBundle (ca. 2.9 MB unzipped) contains the following UDFs and utilities:
      CodeScanner: analyse AutoIt script structure and content, identify potential issues, generate MCF data files CodeCrypter: front-end GUI for the MCF library, for script encryption (without storing the decryption key(s) in the script!) MetaCodeFile UDF (MCF library): for analysis and user-defined alterations of AutoIt script structure and content MCFinclude.au3: #include this UDF in any AutoIt script that you wish CodeCrypter to process CryptoNG, by TheXman; encryption UDF using Bcrypt dll calls (32/64-bit; various algorithms) StoreCCprofile.au3/readCSdatadump.au3/helloworld.au3: auxiliary utilities and example script HowToCodeCrypt.pdf: a simple guide in five steps CodeCrypterFAQ.pdf: questions and answers, partly based upon exchanges in the CodeCrypter thread. MetaCodeTutorial.pdf: the MCF engine explained; useful for encryption, GUI translation, code translation, and much more... Please follow the links for additional information.
    • By TheXman
      Encryption / Decryption / Hashing
      Cryptography API: Next Generation (CNG) is Microsoft's long-term replacement for their CryptoAPI.  CNG is designed to be extensible at many levels and cryptography agnostic in behavior.  Although the Crypt.au3 UDF that is installed with AutoIt3 still works perfectly, the advapi32.dll functions that it uses have been deprecated.  This UDF was created to offer a replacement for the deprecated functions.  According to Microsoft, deprecated functions may be removed in future release.  Therefore, this UDF will be available when/if that happens.
      This UDF implements some of Microsoft's Cryptography API: Next Generation (CNG) Win32 API functions.  In its initial release, it implements functions to encrypt text & files, decrypt text and files, generate hashes, and the Password-Based Key Derivation Function 2 (PBKDF2) function.  The UDF can implement any of the encryption/decryption algorithms or hashing algorithms that are installed on the PC in which it is running.  Most, if not all, of the values that you would commonly use to specify that desired algorithms, key bit lengths, and other magic number type values, are already defined as constants or enums in the UDF file.
      To flatten the learning curve, there is an example file that shows examples of all of the major functionality.  This example file is not created to be an exhaustive set of how to implement each feature and parameter.  It is designed to give you a template or guide to help you hit the ground running in terms of using the functions.  I have tried to fully document the headers of all of the functions as well as the code within the functions themselves.    As of v1.4.0, there is also a Help file that includes all of the functions, with examples.
      Current UDF Functions
      Algorithm-Specific Symmetric Encryption/Decryption Functions _CryptoNG_3DES_CBC_DecryptData _CryptoNG_3DES_CBC_DecryptFile _CryptoNG_3DES_CBC_EncryptData _CryptoNG_3DES_CBC_EncryptFile _CryptoNG_AES_CBC_DecryptData _CryptoNG_AES_CBC_DecryptFile _CryptoNG_AES_CBC_EncryptData _CryptoNG_AES_CBC_EncryptFile _CryptoNG_AES_ECB_DecryptData _CryptoNG_AES_ECB_EncryptData
        Generic Symmetric Encryption/Decryption Functions _CryptoNG_DecryptData _CryptoNG_DecryptFile _CryptoNG_EncryptData _CryptoNG_EncryptFile
        Hashing Functions _CryptoNG_HashData _CryptoNG_HashFile _CryptoNG_PBKDF2
        Asymmetric (Public/Private Key) Encryption/Decryption Functions _CryptoNG_RSA_CreateKeyPair _CryptoNG_RSA_EncryptData _CryptoNG_RSA_DecryptData
        Misc / Helper Functions _CryptoNG_CryptBinaryToString _CryptoNG_CryptStringToBinary _CryptoNG_GenerateRandom _CryptoNG_EnumAlgorithms _CryptoNG_EnumRegisteredProviders _CryptoNG_EnumKeyStorageProviders _CryptoNG_LastErrorMessage _CryptoNG_Version  
      Related Links
      Cryptography API: Next Generation - Main Page
      Cryptography API: Next Generation - Reference
      Cryptography API: Next Generation - Primitives
      Cryptography API: Next Generation - Cryptographic Algorithm Providers
    • By RTFC
      MetaCode offers a way to:
      separate a script's structure from its content remove all redundant definitions (globals and UDFs) change any content (and some structure) combine (new) structure and (new) content into a new script The most useful applications implemented so far are:
      Fast language translation (not just text strings, also variable names and UDF names) Obfuscation (vars and/or UDFs) Script Encryption (conditionals, calls, and macros) Encryption is powerful because the key is not stored anywhere; you can define it to be a user password, macro, environment spec/variable, server response, something you define yourself, or a combination thereof; anything goes, as long as it's not a fixed string or fixed value. More info in the CodeCrypter thread: ?do=embed' frameborder='0' data-embedContent>'?do=embed' frameborder='0' data-embedContent>>
      ?do=embed' frameborder='0' data-embedContent>
      But MetaCode has more potential than that; it allows you to tinker with any type of content separately, then rebuild a new version. So for example, you can have a single script structure and numerous different language modules you just plug in to create a new version in a different language.
      A brief Tutorial is here: MetaCode Tutorial.pdf
      The MCF library itself can be found in the CodeScannerCrypter bundle.
      And a little example how to use it for translating your GUI into a different language:
       UI_Translator.7z (new version that should work with the new version of Google Translate, see post #13 below)
      MCF.au3 is just the library plus the MCFinclude.au3 file you need to include in any script you wish to encrypt.
      There is no GUI here. However, I did write a separate front-end for it called CodeCrypter, which you can find here:
      ?do=embed' frameborder='0' data-embedContent>'?do=embed' frameborder='0' data-embedContent>>
      ?do=embed' frameborder='0' data-embedContent>
      MCF uses output generated by my CodeScanner version 2.8+, which you can find here:
      '?do=embed' frameborder='0' data-embedContent>>
      CodeScanner also depends on MCF.au3 now, as it can now call a few of its functions.
      I should also mention Ward's excellent AES.au3 UDFs used for the encryption and decryption calls,  which is now included in the CodeScannerCrypter bundle (thanks to Ward for allowing to include it). You can find the original (unpatched) version here:
      '?do=embed' frameborder='0' data-embedContent>>
      Note: you can replace the encryption/decryption calls with whatever algorithm you like (hint: the native <Crypt.au3> library is too slow for most purposes, better stick to machine code routines)
      So just to be clear:
      CodeScanner (v2.8+) needs MCF (earlier versions won't work!) CodeCrypter needs MCF (plus anything that MCF needs) MCF itself needs MCFinclude (part of MCF zip) MCF also needs readCSdatadump (part of the CodeScanner package, you need the latest version packaged with CodeScanner v2.8; earlier versions won't work!) both MCF and MCFinclude currently rely on AES.au3 by Ward So you basically need to download the whole bundle for any of it to work.
      If you have any questions, please start by reading the MCF Tutorial and the CodeCrypter FAQ (you can download the latter separately from the CodeCrypter thread).
      Next, read the extensive Remarks sections in MCF.au3, MCFinclude.au3, and CodeCrypter.au3
      If still no joy, then please post. However, I'm not online that often, and logged in to the forum even less, so response may take a while).
    • By Radix

      I would like to know if it is possible to implement an autoit script with GOST algorithm. I noticed that there are seven different algorithms in the standard UDF, but I urgently need a command line crypter with GOST algorithm. I just lack the algorithm part. Is it possible to adapt GPLib in the autoit script?


  • Create New...