User Tools

Site Tools


mmbasic:complex_encryption_uses_rsa_for_asymmetrical_keys

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

mmbasic/complex_encryption_uses_rsa_for_asymmetrical_keys.txt · Last modified: 2024/12/14 20:10 by gerry