Cryptanalysis

General FreeBASIC programming questions.
neil
Posts: 586
Joined: Mar 17, 2022 23:26

Cryptanalysis

Post by neil »

There are two versions of the KnuthRange algorithm via mods. Pick your favorite. Provoni introduced his original algorithm for a 3 Step Text Encryption.The KnuthRange posted here does run a little faster. Provoni's has very strong encryption.

Code: Select all

#define CrLf Chr(10, 13)
#define enc 1
#define dec -1

' ------------------------------------------------------------
Function KnuthRange( Byval seed As UlongInt, Byref BeenHere As Boolean ) As Ubyte
#define IRange( f, l ) Int( _Rand/2^64*( (l+1) - (f) ) + (f) )
Static As Ulongint _Rand
  If BeenHere = False Then
    _Rand = seed
    BeenHere =True
  End If
  _Rand = 6364136223846793005ull * _Rand + 1442695040888963407ull
  Return IRange(0,255)
End Function

Sub EncDec( Byref message As String, Byval seed as Ulongint, Byval rounds As Ulong, ByVal flag As Long )
Dim As ULong  k = Len(message), temp
Dim As Boolean bh
  For i As Ulong = 1 to rounds
    For j As Ulong = 1 To k
      temp = KnuthRange( seed, bh )
      message[j-1] = Asc(message, j) + temp*IIf( (temp <= 128), flag, -flag ) ' Random addition/subtraction
    Next
  Next
End Sub
' ------------------------------------------------------------

' Example usage
Dim s As String
Dim As Double t

s = "The time has come the walrus said" + CrLf
s += "to talk of many things" + CrLf
s += "of shoes, and ships, and sealing wax," + CrLf
s += "of cabbages, and kings," + CrLf
s += "and why the sea is boiling hot," + CrLf
s += "and whether pigs have wings."

Print s + CrLf
t = Timer
EncDec( s, 123456789, 10, enc ) ' Note enc for encryption
t = Timer - t
Print s + CrLf
EncDec( s, 123456789, 10, dec ) ' Note dec for decryption
Print s
Print
Print Int(t*1000000);" microseconds"

Sleep

Here's Provoni's original idea for a 3 Step Text Encryption algorithm. Transposition first, then xor and substitution. It uses 3 key seeds numbers instead of 1: even if the method would be known it would be resistant to brute-force attacks if the seeds are long enough.

Code: Select all

''Provoni's original idea for a 3 Step Text Encryption algorithm.
''Transposition first, then xor and substitution. 
''It uses 3 key seeds numbers instead of 1: even if the method would be known it
''would be resistant to brute-force attacks if the seeds are long enough.
''Maximum seed for the default FreeBASIC random number generator should be 2^32.

function encrypt(s as string,s1 as double,s2 as double,s3 as double)as string
	
	dim as integer i,j,l=len(s)
	dim as integer txt(l-1),key(l-1)
	randomize s1
	for i=0 to l-1 'make key array with numbers from 0 to length-1
		key(i)=i
	next i
	for i=1 to l*l 'shuffle key order
		swap key(int(rnd*l)),key(int(rnd*l))
	next i
	for i=0 to l-2 step 2 'use key to transpose plaintext
		swap s[key(i)],s[key(i+1)]
	next i
	randomize s2
	for i=0 to l-1
		s[i]=s[i]xor(int(rnd*31)+1) 'xor step
	next i
	randomize s3
	for i=0 to l-1
		s[i]+=int(rnd*10) 'one-time pad style substitution
	next i
	return s
	
end function

function decrypt(s as string,s1 as double,s2 as double,s3 as double)as string
	
	dim as integer i,l=len(s)
	dim as integer key(l-1)
	randomize s3
	for i=0 to l-1
		s[i]-=int(rnd*10) 'one-time pad style substitution
	next i
	randomize s2
	for i=0 to l-1
		s[i]=s[i]xor(int(rnd*31)+1) 'xor step
	next i
	randomize s1
	for i=0 to l-1 'make key array with numbers from 0 to length-1
		key(i)=i
	next i
	for i=1 to l*l 'shuffle key order
		swap key(int(rnd*l)),key(int(rnd*l))
	next i
	for i=0 to l-2 step 2 'use key to transpose plaintext
		swap s[key(i)],s[key(i+1)]
	next i
	return s
	
end function

'screenres 640,480,32

? encrypt("The age of AI has begun. Transformers: more than meets the eye.",123456789,987654321,123454321)

? decrypt(encrypt("The age of AI has begun. Transformers: more than meets the eye.",123456789,987654321,123454321),123456789,987654321,123454321)

sleep
Last edited by neil on Apr 15, 2023 21:15, edited 8 times in total.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

Such a short ciphertext is usually impossible to decrypt.

Here's an example:

Code: Select all

8 letter substitution cipher:
40 36 37 34 38 39 35 33

8 unique letters
If the cipher becomes longer then it may become decryptable if one is able to figure out the XOR, substitution and shuffling process, the random number generator(s) and the seeds. Seems like a tall order to me. But with a very long ciphertext allot may become possible especially if some of the encryption steps have weaknesses.

Here's what ChatGPT had to say about it:
To decrypt the 8-letter word, we need to reverse the encryption process. According to the code, there are three main steps to decrypt the word:

1. XOR the characters with the random numbers generated by the seednum.
2. Add the values subtracted during the encryption process.
3. Rearrange the letters to their original positions based on the seednum.

However, we do not have the information about the values subtracted from the original characters during the encryption process or how the characters were rearranged based on the seednum. Without this information, it is not possible to decrypt the 8-letter word.
neil
Posts: 586
Joined: Mar 17, 2022 23:26

Re: Cryptanalysis

Post by neil »

@Provoni
The XOR decryption part is already done. Look at the seed number carefully and notice there are 8 digits. The encrypted word is 8 characters. This should be enough info for the next 2 steps of decryption.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

My interpretation:
'' each variable has 1 encrypted letter in it
a = 86:b = 41:c = 93:d = 75:e = 71:f = 84:g = 93:h = 81
Ciphertext is 86 41 93 75 71 84 93 81
'' seednum was generated from encryption algorithm
seednum=17324865
Seednum is 17324865, numbers from 1 to 8
'' this is the first step of decryption
randomize seednum
Set the seed of the random number generator to seednum.
'' XOR alone would be too weak
for i = 1 to 8
x = (rnd * 31)
if i = 1 Then a = (a xor x)
if i = 2 Then b = (b xor x)
if i = 3 Then c = (c xor x)
if i = 4 Then d = (d xor x)
if i = 5 Then e = (e xor x)
if i = 6 Then f = (f xor x)
if i = 7 Then g = (g xor x)
if i = 8 Then h = (h xor x)
next
This code applies to the ciphertext using the seednum? You stated this part was already done so it can be ignored.
'' the next two steps must be in this order
First substitution then transposition.
'' subtracted values from seednum used for substituting characters
'' needs to be reversed using addition Example a += something from seednum
'' this is used to finish decrypting all letters
This appears to explain reversing the substitution process. For example, a = 86, b = 41, c = 93, somthing from the seednum needs to be added to these numbers. I have no clue how this could work and we would end up with a bigger number that may translate to lowercase letters using the ASCII table?

Example:

84 + 17 (first 2 seed digits) = 101 (letter "e")
41 + 73 (second and third seed digits) = 114 (letter "r")
93 + 32 (third and fourth seed digits) = 125 (no letter) my example failed at this step.
'' then you need to put the letters back in there correct positions from seednum
'' Example something from seednum = letter position
Use seednum as a key to transpose or untranspose the ciphertext. Possible orders: 86 75 93 71 81 93 41 84 or 86 93 93 41 75 81 84 71.
neil
Posts: 586
Joined: Mar 17, 2022 23:26

Re: Cryptanalysis

Post by neil »

@Provoni
All of the letters are in Capitals this could help.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

neil wrote: Apr 09, 2023 7:43 @Provoni
All of the letters are in Capitals this could help.
Uppercase ASCII is from 65 to 90.

86 41 93 75 71 84 93 81

Something from Seednum needs to be added and 93 + x > 90.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

COMPUTER
neil
Posts: 586
Joined: Mar 17, 2022 23:26

Re: Cryptanalysis

Post by neil »

@Provoni
That's correct.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

Code: Select all

'' decrypt.bas this only an experiment in Cryptanalysis.
dim as integer i,j,seednum,l=8,a(l),key(l)
dim as string s,s1,s2,s3

'screenres 640,480,32

'' each variable has 1 encrypted letter in it
a(1)=86:a(2)=41:a(3)=93:a(4)=75:a(5)=71:a(6)=84:a(7)=93:a(8)=81
for i=1 to l
	s1+=str(a(i))+" "
next i
? "Encrypted 8 Letter Word: ";s1

'' seednum was generated from encryption algorithm
seednum=17324865
s=str(seednum)

'' this is the first step of decryption
randomize seednum

'' XOR alone would be too weak
for i=1 to l
	a(i)=a(i)xor(rnd*31)
next

'' unSubstitution
for i=1 to l
	s2+=chr(a(i)+(s[i-1]-48))
next i
?
? "Unsubstituted 8 Letter Word: ";s2

'' unTransposition
for i=1 to l 'invert key
	key(s[i-1]-48)=i
next i
for i=1 to l
	s3+=chr(s2[key(i)-1])
next i
?
? "Untransposed 8 Letter Word: ";s3

sleep
neil
Posts: 586
Joined: Mar 17, 2022 23:26

Re: Cryptanalysis

Post by neil »

@Provoni
Your decryption algorithm is much nicer then mine, I am not going to post my version. Thanks for posting it.
dodicat
Posts: 7983
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Cryptanalysis

Post by dodicat »

This is for the next generation of quantum computers.
In the prng thread we concluded that there were as many random number generators as there are random numbers.
In view of this then pick your favourite generator, select a secret seed, and shuffle your message.

To get your message back, pick your favourite generator (must be the same)
Pick your secret seed (must be the same)
And shuffle your message back to where it was.
This one is called the D1-Anagram-beta, independent of Cook.
(only for the next generation of quantum boxes, further generations may require a tweak)

Code: Select all


#cmdline "-gen gcc -O 2"
#include "crt.bi"
#define range(f,l)  (rand() mod (((l)-(f))+1)) + (f)
#define secretnumber 26

Sub shuffle(a As String)
    dim as long L1=Len(a)-1
    For n As Long = 0 To Len(a)-2
        Swap a[n], a[range((n+1),L1)]
    Next n
End Sub

Sub shuffleback(a As String)
    Dim As Long L=Len(a)-2,L1=Len(a)-1
    redim as long ar(L)
    For n As Long = 0 To Len(a)-2
        ar(L-n)=(range((n+1),L1))
    Next n
    For n As Long=0 To Len(a)-2
        Swap a[L-n],a[ar(n)]
    Next n
End Sub

dim as string text="abcdefghijklmnopqrstuvwxyz ":text+=ucase(text)

for n as long=1 to 17
    text+=text
next

print "Length of text ";len(text)
print mid(text,1,52)+" . . . "+mid(text,len(text)-30)
srand secretnumber
shuffle(text)
print mid(text,1,52)+" . . . "+mid(text,len(text)-30)



srand secretnumber 
shuffleback(text)
print mid(text,1,52)+" . . . "+mid(text,len(text)-30)
print "Done . . ."

sleep
 
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

@neil,

You are looking to use this to encrypt text?

One problem I see is that because of the seed acting as a transposition key with the digits from 0 to 9, it cannot encrypt texts longer than 10 characters. How do you plan to get around that?

Another problem is that both substitution and transposition use the same key.
neil
Posts: 586
Joined: Mar 17, 2022 23:26

Re: Cryptanalysis

Post by neil »

@Provoni
I already knew that. That's why I only selected an 8 Letter word. This was only an experiment. Maybe you have a better idea of how it could be improved or another method altogether. I like this better than working on prng's.
dodicat
Posts: 7983
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Cryptanalysis

Post by dodicat »

Code: Select all

 dim as string g
g=!"vnwe tngenwiodnde h oalah  ,ka fdledeccdi inno nnd ls rh itOns heo'iwm,syoe(atn o\n"
g+=!" nJemdnoshieil tneeD espntonhrd trmi w th pto  ccli k htdi-s rsnn   .icoolh Itlse eeo  a n,kntnl,. IacwtwJo pndtt omcbecshlntusedrrfv .sewp t Am.itcetnutts.spaoueeotI, eo diwy\n"
g+=!"le dteIfiataetnahta geg\n"
g+=!"dfo eghdtystio bcsut),aaetrrerlad  hrra eagnll  aar u t aiap  eta,iuin bgudi .p irnoi nshah?imbosth\n"
g+=!"b erI\n"
g+=!"y nrg n loe  rtos"
hint
Use the default seed.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Cryptanalysis

Post by Provoni »

neil wrote: Apr 09, 2023 9:48 @Provoni
I already knew that. That's why I only selected an 8 Letter word. This was only an experiment. Maybe you have a better idea of how it could be improved or another method altogether. I like this better than working on prng's.
Here's something inspired by your ideas.

Transposition first, then xor and substitution.

3 key seeds numbers instead of 1: even if the method would be known it would be resistant to brute-force attacks if the seeds are long enough. Maximum seed for the default FreeBASIC random number generator should be 2^32.

Use ASCII characters from 32 to 127.

Code: Select all

function encrypt(s as string,s1 as double,s2 as double,s3 as double)as string
	
	dim as integer i,j,l=len(s)
	dim as integer txt(l-1),key(l-1)
	randomize s1
	for i=0 to l-1 'make key array with numbers from 0 to length-1
		key(i)=i
	next i
	for i=1 to l*l 'shuffle key order
		swap key(int(rnd*l)),key(int(rnd*l))
	next i
	for i=0 to l-2 step 2 'use key to transpose plaintext
		swap s[key(i)],s[key(i+1)]
	next i
	randomize s2
	for i=0 to l-1
		s[i]=s[i]xor(int(rnd*31)+1) 'xor step
	next i
	randomize s3
	for i=0 to l-1
		s[i]+=int(rnd*10) 'one-time pad style substitution
	next i
	return s
	
end function

function decrypt(s as string,s1 as double,s2 as double,s3 as double)as string
	
	dim as integer i,l=len(s)
	dim as integer key(l-1)
	randomize s3
	for i=0 to l-1
		s[i]-=int(rnd*10) 'one-time pad style substitution
	next i
	randomize s2
	for i=0 to l-1
		s[i]=s[i]xor(int(rnd*31)+1) 'xor step
	next i
	randomize s1
	for i=0 to l-1 'make key array with numbers from 0 to length-1
		key(i)=i
	next i
	for i=1 to l*l 'shuffle key order
		swap key(int(rnd*l)),key(int(rnd*l))
	next i
	for i=0 to l-2 step 2 'use key to transpose plaintext
		swap s[key(i)],s[key(i+1)]
	next i
	return s
	
end function

'screenres 640,480,32

? encrypt("The age of AI has begun. Transformers: more than meets the eye.",123456789,987654321,123454321)

? decrypt(encrypt("The age of AI has begun. Transformers: more than meets the eye.",123456789,987654321,123454321),123456789,987654321,123454321)

sleep
Post Reply