File Encryption Using Catalan Numbers and Stack Permutation
What are the Catalan Numbers?
A number can be denoted as a Catalan number if its binary form consists of equal number of "1"s and "0"s and start with "1". If “1” represents 'open parenthesis and “0” 'close parenthesis', we can say every open parenthesis closes.
The parenthesis
representation of above number is ” ( ) ( ) ( ( ) ) “.
In same way,
The parenthesis representation is “ (((((()((()))(((()))))())()))()((((()))()((())()()())())))() “
Another
usage of this numbers is Stack Permutation. Here “1” represents PUSH commend
and “0” represents POP commend. In this way an array can be mixed.
n = array size.
= how different
ways n sized array can be mixed.
For example array size is n=30.
So array can be written in 
different ways according
to above formula.
Below there is an example on Stack Permutation.
For
3 characters there are 
different ways.
Number = 
.
Character array = “ abc
”.
|
sequence |
|
operation |
|
|
abc[] |
|
|
+ |
ab[c] |
PUSH c |
|
+ |
a[bc] |
PUSH b |
|
- |
a[c]b |
POP b |
|
- |
a[]cb |
POP c |
|
+ |
[a]cb |
PUSH a |
|
- |
[]acb |
POP c |
So array “ abc “ changed to “ acb ”.
Algorithm can be summarized like this:
Finding Catalan Numbers:
1. Binary array is constructed from number “ s “.
2. In binary array for “ 1 “ usage is “ counter + 1 “ . For “ 0 ” usage is “ counter - 1 “
3.
In WHILE
cycle stay in while counter 
0.
4. After WHILE cycle, if counter = 0, number " s " is Catalan.
Encryption Process:
1. Create a binary array from number “ m “.
2. Using binary array in stack permutation original data is mixed.
Decrypt Process:
1. Create a binary array from number “ m “.
2. In binary array every element is changed: “ 1 ” with “ 0 ” and “ 0 ” with “ 1 ”.
3. Using binary array in stack permutation original data is reconstructed.
Note:
For 60-bit numbers there are 3.814.986.502.092.304 Catalan numbers.
If we try to find all Catalan numbers and write to disk, required space is:
for binary file
30.519.892.016.738.432 byte
= 29.804.582.047.596 KB
= 29.106.037.155 MB
= 28.423.864 GB
= 27.757 TB
Suppose all 60-bit Catalan numbers were calculated.
If for every number average control time is 1 ms, test time will be 120972 years.
Average time will be 
years.
Here are some 60-bit Catalan numbers for you.
The Algorithm
Win32 Source Code (Visual C++)
Files are used for test purposes. File name entrance should be changed.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define chr_num 30
long filesize(FILE* stream) {
long curpos, length;
curpos = ftell(stream);
fseek(stream, 0L, SEEK_END);
length = ftell(stream);
fseek(stream, curpos, SEEK_SET);
return length;
}
int find_catalan()
{
short A[67];
__int64 i, k, m, n, s, count, cstart, cend ;
FILE *fl;
cstart = 576460752303423488;
cend = 1152921503533105152;
k = 0;
s = cstart; // 60-bit = 30 character.
while ( s < cend )
{
m = s;
n = 0;
while(m > 1)
{
if ( (m&1) > 0)
A[n] = 1;
else
A[n] = 0;
n++;
m = m >> 1;
}
A[n] = 1;
n++;
count = 0;
i = n - 1;
while ( (i>=0) && (count>=0) )
{
if (A[i] == 1)
count++;
else
count--;
i--;
}
if( count == 0 ) // number is catalan
{
fprintf(fl,"%I64d\n",s);
}
s++;
}
fclose(fl);
return 0;
}
int encrypt_catalan()
{
short A[67];
char buf1[chr_num], buf2[chr_num], buf3[chr_num], ch;
__int64 i, j, k, m, n, s, L1, L2, L3;
long int count = 0;
FILE *fl1, *fl2;
fl1 = fopen("z.txt","rb");
fl2 = fopen("z2.txt","wb");
m = 1142920503053891760; // used catalan number.
n = 0;
while(m > 1)
{
if ( (m&1) > 0)
A[n] = 1;
else
A[n] = 0;
n++;
m = m >> 1;
}
A[n] = 1;
count = filesize(fl1) / chr_num;
for (j=0;j<count;j++)
{
fread(&buf1, chr_num, 1, fl1);
L1 = chr_num-1;
L2 = L3 = 0;
for(i=n;i>=0;i--)
if (A[i] == 1) // PUSH
{
buf2[L2] = buf1[L1];
L2++;
L1--;
}
else // POP
{
buf3[L3] = buf2[L2-1];
L2--;
L3++;
buf2[L2] = 0;
}
fwrite(&buf3, chr_num, 1, fl2);
}
count = filesize(fl1) - ftell(fl1);
fread(&buf1, count, 1, fl1);
fwrite(&buf1, count, 1, fl2);
fclose(fl1);
fclose(fl2);
return 0;
}
int decrypt_catalan()
{
short A[64];
char buf1[chr_num], buf2[chr_num], buf3[chr_num], tmp;
__int64 i, j, k, m, n, s, L1, L2, L3;
long int count = 0;
FILE *fl1, *fl2;
fl1 = fopen("z2.txt","rb");
fl2 = fopen("z3.txt","wb");
m = 1142920503053891760; // used catalan number.
n = 0;
while(m > 1)
{
if ( (m&1) > 0)
A[n] = 1;
else
A[n] = 0;
n++;
m = m >> 1;
}
A[n] = 1;
for(i=0;i<=n;i++)
A[i] = A[i] ^ 1;
count = filesize(fl1) / chr_num;
for (j=0;j<count;j++)
{
fread(&buf1, chr_num, 1, fl1);
L1 = chr_num - 1;
L2 = L3 = 0;
for(i=0;i<=n;i++)
if (A[i] == 1)
{
buf2[L2] = buf1[L1];
L2++;
L1--;
}
else
{
buf3[L3] = buf2[L2-1];
L2--;
L3++;
}
fwrite(&buf3, chr_num, 1, fl2);
}
count = filesize(fl1) - ftell(fl1);
fread(&buf1, count, 1, fl1);
fwrite(&buf1, count, 1, fl2);
fclose(fl1);
fclose(fl2);
return 0;
}
void main(void)
{
find_catalan();
encrypt_catalan();
decrypt_catalan();
}
Sample Execution
For 30 characters a 60-bit catalan number is required.
Used
number is: 
Original Text File
TASM now supports aliasing. This means that TASM allows the association
of an alias name with another name ( called the substitute name ) in a
program. Any time that alias name is encountered it will really refer
to the substitute name.
Aliasing is primarily a linker issue. The alias statement will generate
an alias record setting the alias name equal to the substitute name,
e.g.: 000056 ALIAS '_Set_Coords' = '_SetCoords'
When the linker tries to resolve a reference to a name and it finds an alias
record for that name, it will continue trying to resolve the reference
using the substitute name.
Encrypted Text File
nasi aligs.t rsupp ooM nSTAwTwlloSM asA Tth thasta meshinesliaan a nfamoion
t
isocs aaelcale ( emda tnthero ath i wnh n a ) i
e
mpraute tntubsse ioaalihat st naey tinm m. agrAm illit wr edaleunteorns eie clutitsubst ee nh
to
trefery alariprimy sa isinga l
A.meilsas aliteahteTue. s ier kinsmi al
anaest ragene rl witenleas naliam ee ehing tted srcotqm natuteei,t
se suhb toluate_ ' SSeAt_I56 A0L0: 0..g0Ch
Wrds'eono tC'_Se t ds'roo=heolv res oat r trie seinkle re it andfeimndao a tneencrfe shr td foarto nc
rsei aln aaaitrynue nigt tnll cio it,mewo
e
rencuesfinethe rvsole reg the substitute name.
Decrypted Text File
TASM now supports aliasing. This means that TASM allows the association
of an alias name with another name ( called the substitute name ) in a
program. Any time that alias name is encountered it will really refer
to the substitute name.
Aliasing is primarily a linker issue. The alias statement will generate
an alias record setting the alias name equal to the substitute name,
e.g.: 000056 ALIAS '_Set_Coords' = '_SetCoords'
When the linker tries to resolve a reference to a name and it finds an alias
record for that name, it will continue trying to resolve the reference
using the substitute name.
Some 60-bit Catalan Numbers
|
768614336404564650 768614336404564652 768614336404564658 768614336404564660 768614336404564664 768614336404564682 768614336404564684 768614336404564690 768614336761727106 768614336761727108 768614336761727112 768614336761727120 768614336761727136 768614336761727168 768614336761727234 768614336761727236 768614336761727240 768614336762350592 768614336762351618 768614336762351620 768614336762351624 768614336762351632 768614336762351648 768614336762351680 768614336762351744 768614336762351872 768614336762352128 768614336762352640 768614336762353664 768614336762355714 768614336762355716 768614336762355720 768614336762355728 768614336762355744 768614336762355776 768614336762355840 768614336762355968 768614336762356224 998914336762363914 998914336762363916 998914336762363922 998914336762363924 998914336762363928 998914336762363938 998914336762363940 998914336762363944 998914336762363952 998914336762363970 998914336762363972 998914336762363976 |
998914336766534658 998914336766534660 998914336766534664 998914336766534672 998914336766534688 998914336766534720 998914336766534784 998914336766534912 998914336766535168 998914336766535682 998914336766535684 998914336766535688 998914336766535696 998914336766535712 998914336766535744 1102921503000000002 1102921503000000004 1102921503000000008 1102921503000000016 1102921503000000032 1102921503000000064 1102921503000000128 1102921503000000256 1102921503000000522 1102921503000000524 1102921503000000530 1102921503000000532 1102921503000000536 1102921503000000546 1102921503000000548 1102921503000000552 1102921503000000560 1102921503000000578 1102921503000000580 1102921503000000584 1102921503000000592 1102921503000000608 1102921503000000642 1102921503000000644 1102921503000000648 1102921503000000656 1102921503000000672 1102921503000000704 1102921503002340194 1102921503002340196 1102921503002340200 1102921503002340208 1102921503002340234 1102921503002340236 1102921503002340242
|
1132921503012432770 1132921503012432772 1132921503012432776 1132921503012432784 1132921503012432800 1132921503012432832 1132921503012432938 1132921503012432940 1132921503012432946 1132921503012432948 1132921503012432952 1132921503012848690 1132921503012848692 1132921503012848696 1132921503012848714 1132921503012848716 1132921503012848722 1132921503012848724 1132921503012848728 1132921503012848738 1132921503012848740 1132921503012848744 1132921503012848752 1132921503012848778 1132921503012848780 1132921503012848786 1132921503012848788 1132921503012848792 1132921503012848802 1132921503015128594 1132921503015128596 1132921503015128600 1132921503015128610 1132921503015128612 1132921503015128616 1132921503015128624 1132921503015128642 1132921503015128644 1132921503015128648 1132921503015128656 1132921503015128672 1132921503015128706 1132921503015128708 1132921503015128712 1132921503015128720 1132921503015128736 1132921503015128768 1132921503015128834 1132921503015128836 1132921503015128840
|
1142920503052433408 1142920503052435498 1142920503052435500 1142920503052435506 1142920503052435508 1142920503052435512 1142920503052435530 1142920503052435532 1142920503052435538 1142920503052435540 1142920503052435568 1142920503052435594 1142920503052435596 1142920503052435602 1142920503052435604 1142920503052435608 1142920503052435618 1142920503052435620 1142920503054538050 1142920503054538052 1142920503054538056 1142920503054538064 1142920503054538080 1142920503054538114 1142920503054538116 1142920503054538120 1142920503054772500 1142920503054772504 1142920503054772514 1142920503054772516 1142920503054772520 1142920503054772528 1142920503054772546 1142920503054772548 1142920503054772552 1142920503054772560 1142920503054772576 1142920503054772610 1142920503054772612 1142920503054772616 1142920503054772624 1142920503054772640 1142920503054772672 1142920503054772746 1142920503054772748 1142920503054772754 1142920503054772756 1142920503054772760 1142920503054772770 1142920503054772772
|