Complex Encryption Uses RSA For Asymmetrical Keys
Articles elsewhere on this wiki discuss the use of encryption to hide the contents of (primarily) data transmitted on an open or easily tapped medium.
Those articles include
- Straightforward obfuscation - just making it difficult to read what is being transmitted with something like Base64 - not encryption because there is no key and the resultant strings are generated procedurally.
- Simple encryption using a shared key and XORing each character of the data with each in a shared key. This is acceptable for most circumstances where the data is not terribly interesting and speed is required. A major problem is that a given character in the same place in the input will always generate the same character in the output, so it can be decrypted by “card-counting” methods.
- Strong encryption using comercial grade RC4 which uses a shared key but the encryption requires multiple rounds so the output is not a simple factor of the input and the key, and unlike simple XORing, characters will generate different output characters depending on the key, their place in the input etc… RC4 is considered deprecated today but with a good length key is still fine for most non-critical data. Using a SALT on the front of the key can greatly enhance the encryption. It doesn't have to be as complex as that article, which is more concerned with HASHing rather than encryption - I'll do an article on how to produce and use a SALT at a later date.
The above all have weaknesses and strengths which must be evaluated against the application - doubly so in the arena of microcontrollers where memory and CPU speed are often at a premium. It depends on how sensitive the comms are. If you just want to make it difficult for snoopers, then the first two are a good fit. If the traffic could be deemed sensitive or vulnerable to spoofing, then you really should consider something like RC4 as it is still; reasonably fast, “proper” encryption. You do, of course, have to take steps to obscure symmetrical keys in the source code - not so with “Asymmetrical Keys” (AK).
These articles have danced around the subject of AK. The above use the same key to both encrypt and decrypt the data and this increases the opportunities for the key to become known. AK really shuts this exposure down as there are two keys, a public and a private key. The public key should be widely known and is used to encrypt the data. It cannot, however, be used to decrypt it. This is through the use of some clever maths that uses two prime numbers to form the keys. The first is known (the public key) but the second is private. Only by knowing this second prime can the resultant product be determined and the data decrypted. Yes you could brute force it and this is why huge primes are of interest to cryptography… and why that is a problem for microcontrollers…
RSA (the initials of it's inventors) is a public/private keyed encryption algorithm used widely on powerful systems that can handle the huge primes needed - vital if the data is to stay safe.
Large primes (those with hundreds of digits) make RSA incredibly secure but are very difficult to work with in small processors. In reality, any two primes will do and the small ones (say up to 1,000) will encrypt the data admirably, but are also very easy to brute-force; a modern PC would break the encryption in a fraction of a second. Sadly, meaningful primes; those way beyond, result in keys (integers) so large they break the math engine or simply take too much effort on small processors. Specialised hardware solutions do exist but are very expensive.
Really good RSA requires really big primes (key files can be tens of MegaBytes), and really big primes require super-fast processors to go through the decryption process in anything like workable times, it generally makes software RSA unsuitable for microcontrollers. The only way you can make it viable is to deliberatley weaken the strength of the keys (by using smaller primes) - what's the point?
The large integers generated by the keys have a direct impact on the time required to encrypt and decrypt the data - the data is in a processing loop and even though it's fairly simple, the more times round the loop the longer it takes. Because RSA works on single bytes, outputting an integer for each byte of input. To de/encrypt a text message you'll need to go through the process a number of times, so the time taken is directly a function of the length of the input string.
As an aside; RSA “parallelizes” really well, e.g. multiple cores can work on individual bytes simultaneously. Combining the simple maths and the “byte-by-byte” approach, GPUs are particularly useful. High-end/Gaming GPUs can have thousands of cores meaning the entire message can be attacked, legitimately or not, in large pieces “from the side”. This is a point not lost on hackers.
For completeness, below is a version of RSA encryption that is fully compliant and enrypts/decrypts one byte “messages” into their resultant integers. You can see the actual de/encryption process is really simple. I also include the first 200 primes so you have some to hand if you want to play. You'll see how various combinations of E, P and Q affect the timings.
Usually, the key generation code would be a seperate program, used rarely and kept securely, to provide keys to be used in the application code.
Functional code is either an encrypter or decrypter and would not have both the E and D primes (nor the associated Encryption and Decryption functions). From this then, it follows that AK is not bi-directional by nature. This is seen from its common usage in applications such as email and data warehousing etc. where spontaneous message/reply and fast turn-around is not generally required. The data being stored, indefinitely, in its encrypted form and only decrypted if/when required.
Follow the program flow to see that you have to set your primes then generate your keys, as a one-time action, before you can start encrypting.
Enjoy
'MMBasic example of RSA asymmetrical encryption 'first 200 primes for playing with E, P & Q '2 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 'these variable names are the standard names associated with RSA. 'by convention, I always capitalize global variables and it helps here 'due to the brief nature of them Const E=373,P=53,Q=47' primes for keying Dim Integer D,N,M Dim ciphertext As Integer' the integer that represents an encrypted char Dim decryptedMessage As String Dim T$ 'Step 1: Generate RSA keys GenerateRSAKeys ? "Public key: (";E;",";N;") share liberally" ? "Private key: (";D;",";N;") keep secret" 'Step 2: Encrypt a message ' RSA only encrypts single characters. Documentation can be 'mis-leading in that m is not natively multi-character 'so we have to loop through each character adding new integers to 'a "block" of integers, each representing a single character... 'the following demonstrates the single-char nature... T$="woot" ? "Original message: " ,T$ timer=0 ciphertext=EncryptByte(T$) ? "Encrypted Integer (ciphertext): ",ciphertext,timer 'Step 3: Decrypt the message timer=0 decryptedMessage=DecryptByte$(ciphertext) ? "Decrypted message: ", decryptedMessage,timer 'Function to generate RSA and private keys Sub GenerateRSAKeys() N=P*Q D=ModInverse((P-1)*(Q-1)) End Sub Function EncryptByte(b$) As Integer Local Integer i,c=1 For i=1 To E c=((c*Asc(b$)) Mod N) Next EncryptByte=c End Function Function DecryptByte$(c As Integer) Local Integer i M=1 For i = 1 To D M=(M*c) Mod N Next DecryptByte$=Chr$(M Mod 256) End Function '### Support functions ### 'Function to find modular inverse (extended Euclidean algorithm) Function ModInverse(phi As Integer) As Integer Local Integer t,newT=1,r=phi,newR=E,quotient,tmpT,tmpR While newR quotient=r\newR tmpT=t:t=newT:newT=tmpT-quotient*newT tmpR=r:r=newR:newR=tmpR-quotient*newR Wend If r>1 Then ? "Modular inverse does not exist" Exit Function End If If t<0 Then t=t+phi End If ModInverse=t End Function