lowbyte1
24.02.2010, aktualisiert am 24.08.2010
view13438
view1
3
Goto Top

Kryptoanalyse - Mustersuche (Patternsearch) Program zur Entschlüsselung von monoalphabetisch Substituiertem Text

AnleitungC, C++Entwicklung
XOR-BASE
http://vpn23.homelinux.org

back-to-topMusteranalyse Programm Mustersuche.c v.1.0.4 beta


Als Mustersuche wird in der Kryptologie eine klassische Methode zur Entzifferung von Geheimtexten bezeichnet. Sie wird auch „Methode des Wahrscheinlichen Wortes“ genannt. Die Mustersuche wird zum brechen von monoalphabetischem Substituiertem Text verwendet. Sie ist auch dan noch effizient wen die Häufigkeitsanalyse nicht mehr funktioniert, aufgrund zu kurzer länge des Textes.
Dabei weiß, vermutet oder errät der Codeknacker, dass im zu entziffernden Geheimtext eine bestimmte Phrase (Crib) auftritt. Gelingt es, die genaue Lage (Position) dieser Phrase im Text zu ermitteln, dann ist bei einigen Verschlüsselungsverfahren ein Einbruch erzielt, der häufig ausreicht, um die Verschlüsselung vollständig zu brechen.




Mein Program ist in C geschrieben, und wurde mit einem VC++08 Compiler getestet.


back-to-topEin kleines Example:

Plaintext : "DIE MONOALPHABETISCHE SUBSTITUTION IST SEHR UNSICHER UND KANN MIT DER MUSTERSUCHE GEKNACKT WERDEN"

Key : "XWYZVUTLSMRQPONGHKJIFEDCAB"

Cyphertext : "ZSV PNONXQGLXWVISJYLV JFWJISIFISNO SJI JVLK FOJSYLVK FOZ RXOO PSI ZVK PFJIVKJFYLV TVROXYRI DVKZVO"


back-to-topProgram Ablauf :

- Pattern search - Crypto breaking system - v.1.0.1


Filename of plaintext :test.txt


Ciphertext :

ZSV PNONXQGLXWVISJYLV JFWJISIFISNO SJI JVLK FOJSYLVK FOZ RXOO PSI ZVK PFJIVKJFYLV TVROXYRI DVKZVO



Input "crib" max 20 byte :SUBSTITUTION  


Crib pattern :1,2,3,1,4,5,4,2,4,5,6,7,



Total gibt es 86 Muster f³r den Text


01. 1,2,3,4,5,6,7,6,8,9,10,11,
02. 1,2,3,4,5,6,5,7,8,9,10,7,
03. 1,2,3,4,5,4,6,7,8,9,6,10,
04. 1,2,3,4,3,5,6,7,8,5,9,10,
05. 1,2,3,2,4,5,6,7,4,8,9,10,
86. .....

Muster / Crib gefunden bei Position -> 23



Crib bei Textposition ersetzen ? <y/n> :y


Text anzeigen ? <y/n> :y


ZSV PNONXQGLXWVISJYLV SUBSTITUTION SJI JVLK FOJSYLVK FOZ RXOO PSI ZVK PFJIVKJFYLV TVROXYRI DVKZVO



Text wiederherstellen ? <y/n> :n


Equ Zeichen ersetzen ? <y/n>:y


Text anzeigen ? <y/n> :y


ZIV PONOXQGLXBVTISYLV SUBSTITUTION IST SVLK UNSIYLVK UNZ RXNN PIT ZVK PUSTVKSUYLV TVRNXYRT DVKZVN



Analyse dieses crib abbrechen <y> ? / Weitere Positionen im Text, auf crib-muster pr³fen <w> ? :

Danach kann mit weiteren "Crib" probiert werden bis schlussendlich der Klartext ersichtlich ist.

back-to-topSource code :

//=========================================================================
//
// File    : muster_suche.c Crypto-analyse (pattern search) v.1.0.4
//
// Author  : Lowbyte
//                           
// Create  : 22.02.2009, 03:27,  Long******
//
// Last Up : 26.02.2009, 05:01,  Long******
//
// Prog.L  : C
//
// Project : 0004K
//
//=========================================================================

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int make_sig_of_crib(unsigned char *crib_buf);
int make_sig_of_ptext(unsigned char *filename ,int flen ,int criblen);
int char_exchange(unsigned char *ptext ,unsigned char *orgptext ,unsigned char *crib ,int cribpos);
int savepos(int pos ,int len);

/* Muster struktur */
typedef struct {

	unsigned char ptext_pattern[10000][20];
	unsigned char crib_pattern[20];

} Pattern;

/* Positionen schützen */
typedef struct {

	int stack[10000];
	int count;

} ProtectedField;


Pattern ctx;
ProtectedField pfctx = {0,0};

int main()
{
	FILE *file; // Filepointer
	unsigned char *p ,*orgp; // Heap
	unsigned char filename[100]; // Filename
	unsigned char crib[22]; // Crib
	char yn[3];
	int x=0 ,rc=0 ,clen=0 ,flen=0 ,flag=0 ,choice=0 ,i=0;
	errno_t er;


	printf_s("- Pattern search - Crypto breaking system - v.1.0.1\n\n");  


	/* Input filename */
	printf_s("\nFilename of plaintext :");  
	fgets(&filename ,100 ,stdin);
	filename[strlen(filename)-1]='\0';  

	/* File öffnen */
	er = fopen_s(&file ,filename ,"r+b");  
	if(er != 0){
		printf_s("\nDateikonnte nicht geöffnet werden\n");  
		getchar();
		return 1;
	}
	/* Grösse des text in byte ermitteln */
	fseek(file, 0L, SEEK_END);
	flen = ftell(file);

	/* Zeiger auf anfang der Datei */
	rewind(file);

	/* Nötiger Speicher vom Heap reservieren */
	p = (unsigned char *)malloc((2+flen) * sizeof(unsigned char));
	if(p == NULL) {
		printf_s("\n\nMemory allocation failure\n\n");  
		getchar();
		exit(1);
	}

	/* Text einlesen */
	fgets(p ,flen+2, file);
	p[flen]='\0';  

        /* File schliessen */
        fclose(file);

	/* Text anzeigen */
	printf_s("\n\nCiphertext :\n\n%s\n\n", p);  

	do
	{

		/* Input scrib max 20 byte & crib <= ptextlen*/
		printf_s("\n\nInput \"crib\" max 20 byte :");  
		fflush(stdin);
		fgets(&crib ,22 ,stdin);
		crib[strlen(crib)-1]='\0';  

		/* Signatur des crib erstellen */
		make_sig_of_crib(crib);

		/* Signatur des textes berechnen */
		make_sig_of_ptext(p ,flen ,(int)strlen(crib));

		/* Signaturen vergleichen */
		for(x=0;x<((flen-(int)strlen(crib))+1);x++) {

			if( memcmp( &ctx.crib_pattern ,&ctx.ptext_pattern[x] ,strlen(crib) ) == 0){

				/* Flag setzen (Muster gefunden) */
				flag=1;
				/* Muster gefunden */
				printf_s("\n\nMuster / Crib gefunden bei Position -> %i \n\n",x+1);  

				/* pText zwischen speichern */
				/* Nötiger Speicher vom Heap reservieren */
				orgp = (unsigned char *) malloc((2+flen) * sizeof(unsigned char));
				if(orgp == NULL) {
					printf("\nMemory allocation failure !\n\n");  
					getchar();
					exit(1);
				}
				memcpy(orgp ,p ,flen);
				orgp[flen]='\0';  

				/* Crib mit textposition ersetzen */
				fflush(stdin);
				printf_s("\n\nCrib bei Textposition ersetzen \? <y/n> :");  
				fgets(yn ,2 ,stdin);

				if(yn == 'y') {  

					/* crib ersetzen */
					memcpy(&p[x] ,&crib ,strlen(crib));

					/* Text anzeigen */
					fflush(stdin);
					printf_s("\n\nText anzeigen ? <y/n> :");  
					fgets(yn ,2 ,stdin);
					if(yn == 'y') {  
						printf_s("\n\n%s\n\n",p);  
					}

					/* Text recovery */
					fflush(stdin);
					printf_s("\n\nText wiederherstellen ? <y/n> :");  
					fgets(yn ,2 ,stdin);
					if(yn == 'y') {  

						/* Wiederherstellen */
						memcpy(&p ,&orgp ,flen);
						orgp[flen]='\0';  

					} else {

						/* Position des crib speichern / gegen ersetzung schützen */
						savepos( x ,(int)strlen(crib));

						/* Equalente Zeichen vom Crib und des Textes ersetzen */
						fflush(stdin);
						printf_s("\n\nEqu Zeichen ersetzen ? <y/n>:");  
						fgets(yn ,2 ,stdin);
						if(yn == 'y') {  
							char_exchange(p ,orgp ,crib ,x);
						}

					}

					/* Speicher bereich freigeben */
					free(orgp);
					

					/* Text anzeigen */
					fflush(stdin);
					printf_s("\n\nText anzeigen ? <y/n> :");  
					fgets(yn ,2 ,stdin);
					if(yn == 'y') {  
						printf_s("\n\n%s\n\n",p);  
					}

				} /* cmp end */


				/* Analyse vorzeitig abbrechen und neuer crib testen ? y\n? */
				fflush(stdin);
				printf_s("\n\nAnalyse dieses crib abbrechen <y> ? / Weitere Positionen im Text, auf crib-muster prüfen <w> ? :");  
				fgets(yn ,2 ,stdin);
				if(yn == 'y')  
					break;	/* Aus schleife springen */

			}

			if(yn == 'y')  
				break;	/* Aus schleife springen */

		}

		if(flag == 0) {
			/* Keine Muster gefunden */
			printf("\n\nEs wurden keine Muster gefunden !\n\n");  
		}
		/* Flag zurücksetzen */
		flag = 0;

		/* Analyse vollstaendig abbrechen \\ neuer crib testen y\n? */
		fflush(stdin);
		printf_s("\n\nAnalyse vollstaendig abbrechen <y> ? / Neuer crib testen <n> ? :");  
		fgets(yn ,2 ,stdin);
		if(yn == 'y') {  
			choice=0;
		} else {
			choice=1;
		}

	}
	while(choice != 0 );


	free(p);
	getchar();

	return 0;
}


/* Muster des crib erstellen */

int make_sig_of_crib(unsigned char *crib_buf)
{

	int i, c;
	int counter=1 ,slen=0;

	/* set var to zero */
	memset(ctx.crib_pattern ,0 ,21);

	slen = (int)strlen(crib_buf);

	for(i=0 ; i<slen ; i++) {
		if(i==0){
			ctx.crib_pattern[i] = 1;
		} else {
			for(c=0 ; c<slen && c<i ; c++) {
				if(crib_buf[i] == crib_buf[c]) {
					ctx.crib_pattern[i] = ctx.crib_pattern[c];
				}
			}

			if(ctx.crib_pattern[i] == 0) {
				ctx.crib_pattern[i] = ++counter;
			}
		}

	}

	printf_s("\n\nCrib pattern :");  
	for(i=0;i<slen;i++){
		printf_s("%i,",ctx.crib_pattern[i]);  
	}

	getchar();

	return 0;

}



/* Signatur / Muster des verschlüsselten Text erstellen */

int make_sig_of_ptext(unsigned char *p ,int flen ,int criblen)
{

	int counter=1;
	int i ,c ,s ,range;



	/* Initialisiere struct var */
	for(i=0;i<flen;i++) {
		memset(&ctx.ptext_pattern[i] ,0 ,21);
	}

	/* Text range berechnen */
	range = ((flen-criblen)+1);

	/* Alle Muster berechnen und in struktur speichern */
	for(s=0;s<range;s++) {

		for(i=0 ; i<criblen ; i++) {
			if(i==0){
				ctx.ptext_pattern[s][i] = 1;
			} else {

				for(c=0 ; c<criblen && c<i ; c++) {
					if(p[i+s] == p[c+s]) {
						ctx.ptext_pattern[s][i] = ctx.ptext_pattern[s][c];
					}
				}
				if(ctx.ptext_pattern[s][i] == 0) {
					ctx.ptext_pattern[s][i] = ++counter;
				}
			}

		}

		counter = 1;

	}

	printf_s("\n\n\nTotal gibt es %i Muster für den Text\n\n",range);  
	for(c=0;c<range && c<5;c++) {
		printf_s("\n%.2i. ",c+1);  
		for(s=0;s<criblen;s++){
			printf("%i,",ctx.ptext_pattern[c][s]);  
		}
	}
	if(range>5) {
		printf_s("\n%.2i. .....",range);  
	}

	return 0;
}


/* Buchstaben austausch funktion */

int char_exchange(unsigned char *ptext ,unsigned char *orgptext ,unsigned char *crib ,int cribpos)
{

	int i ,x ,y ,flag=0;
	int criblen ,ptextlen;

	ptextlen = (int)strlen(ptext);
	criblen = (int)strlen(crib);

	for(i=0;i<criblen;i++) {

		for(x=0;x<ptextlen;x++) {

			if( orgptext[cribpos+i] == orgptext[x] ) {
				for(y=0;y<pfctx.count;y++) {
					if(pfctx.stack[y] == x) {
						flag = 1;
					}
				}
				if(flag == 0) {
					ptext[x]= crib[i];
					/* Position schützen */
					savepos( x ,1);
				}
				flag = 0;
			}

		}
	}

	return 0;

}


/* Positions schutz funktion */
int savepos(int pos ,int len)
{
	int i;

	for(i=0;i<len;i++) {
		pfctx.stack[pfctx.count + i] = pos+i;
	}

	pfctx.count += len;

	return 0;

}


lowbyte
ShareTeilen
Auf Facebook teilen Auf Twitter teilen Auf Reddit teilen Auf Linkedin teilen

Content-ID: 136792

Url: https://administrator.de/contentid/136792

Ausgedruckt am: 23.11.2024 um 06:11 Uhr

1 Kommentar
Goto Top
lowbyte1
lowbyte1 25.02.2010 um 02:13:49 Uhr
Goto Top
Hi crypto freaks

Das Program hat noch Beta status und wird erweitert.

v.1.0.1 ersetzt
v.1.0.2 ersetzt
v.1.0.3 ersetzt
Aktuelle Version v.1.0.4



lowbyte
AnleitungC, C++Entwicklung
Mehr von lowbyte1lowbyte1Fast compression library for C, C and Javalowbyte1 - 3 Kommentarelowbyte1Welcome - OpenCV Wikilowbyte1 - 2 Kommentarelowbyte1SPC23 - 512-Bit Block Cipher Algorithmlowbyte1lowbyte1Prozess ermitteln der diesen Ordner erstelltlowbyte1 - 6 Kommentare
Heiß diskutiert
superfun2k24Sophos SFOS 20 DNAT funktioniert nichtsuperfun2k24 - 26 Kommentareuser217Kaufberatung Hardware - Hyper-V Cluster 3 Nodesuser217 - 25 KommentarePharaunIntel-E810 QSFP28 to Mikrotik QSPF+ mit 40Gbit VerbindungPharaun - 24 Kommentareprplemk2Testumgebung bauen (Grundlegend)prplemk2 - 19 KommentareaufdemmarsHP Z620 USB hat kein Strom beim Startenaufdemmars - 17 KommentareTJ.Hooker74Dom.Admin-Passwort ändern - Auswirkungen auf EX, HCW, AADCTJ.Hooker74 - 15 KommentareUnluckyProccess1999Creo 4.0 Lizenz Server (LMTOOLS)UnluckyProccess1999 - 13 KommentaremaisenkaiserSwitch ohne STP ins Netzwerkmaisenkaiser - 13 KommentareJudgelgZertifikate in die Exchange Online GAL hochladenJudgelg - 13 KommentareadmtechEntwicklertagebuch: Release 6.4 - Filteradmtech - 13 KommentareleberkaeseFB7590 ISDN Fax-Funktionleberkaese - 12 KommentareZZaaiiggaaEDIFACT - Keins vorhanden ?ZZaaiiggaa - 11 Kommentare