Tävlingsprogrammering/Uppgifter/Kryptering

Kryptering

En måttligt framgångsrik bataljon använder sig av en variant av Vignère-krypto för att kryptera sina meddelanden. Man använder sig av en bokstavssnurra (se figur ovan) som består av två ringar med bokstäverna i alfabetet (A-Z) där den inre kan förskjutas i förhållande till den yttre. När man krypterar sitt meddelande så letar man rätt på bokstaven på den inre skivan men i den krypterade texten skriver man istället motsvarande bokstav på den yttre skivan. För att förvilla fienden så snurrar man den inre skivan ett antal steg (medurs) mellan kodningen av varje bokstav. Och för att göra det extra svårt så snurrar man inte lika många steg varje gång utan man ökar antalet steg med ett konstant värde varje gång. Dessutom kan snurran ha vilket läge som helst när man börjar koda. Du har kommit på ett sätt att knäcka koden: du har nämligen upptäckt att alla meddelanden börjar med HEJ. Skriv ett datorprogram som, givet den krypterade texten skriver ut det ursprungliga meddelandet. Meddelandet innehåller endast versalerna A-Z (alltså t.ex. inga blanksteg) och är mellan 3 och 20 bokstäver långt.

Körningsexempel 1: Krypterad text ? LRIJOUZRIYAQIRAG

Meddelande: HEJVITARENFIKANU

Körningsexempel 2: Krypterad text ? GCGDJJI

Meddelande: HEJHOPP

Lösning

Linjärt ekvationssystem

Problemet kan på ett enkelt sätt lösas med hjälp av ett linjärt ekvationssystem. För att göra det på ett enkelt sätt kan man använda ett språk som har inbyggt stöd för sådana, som exempelvis MATLAB.

Lösningsförslag i MATLAB:

   function svar = kryptering()
        global letters;
        letters='ABCDEFGHIJKLMNOPQRSTUVWXYZ';
        beginning='HEJ';
        global ABC; global Encrypted;
        Encrypted = input('Ange krypterat meddelande ? ');
        Matr=[1 1 1; 1 2 4; 1 3 9];
        ABC=zeros(3,1);
        HL=zeros(3,1);
        for i =1:3
              HL(i,1)=leastCycle(Encrypted(1,i),beginning(1,i));
        end
        while HL(2,1)<HL(1,1) 
              HL(2,1)=HL(2,1)+size(letters,2);
        end
        while HL(3,1)<HL(2,1)
              HL(3,1)=HL(3,1)+size(letters,2);
        end
        ABC=Matr\HL;
        svar=Encrypted;
        for i = 1:size(Encrypted,2)
              svar(1,i)='A'+getLetter(Encrypted(i),i);
        end
        return;
   end

   function s = leastCycle(U,V)
        global letters;
        slingvar = U-'A'+1;
        while letters(1,slingvar)~=V
               slingvar=slingvar+1;
               if slingvar>size(letters,2)
                     slingvar=1;
               end
        end
        s=slingvar-(U-'A'+1);
        if s<0
               s=s+size(letters,2);
        end
        return;
    end

    function shift = getLetter(E, tal)
        global letters;
        global ABC;
        shift=E+ABC(1,1)+ABC(2,1)*tal+ABC(3,1)*tal*tal-'A';
        while shift>size(letters,2)-1
              shift=shift-size(letters,2);
        end
        while shift<0
              shift=shift+size(letters,2);
        end
        return;
    end

Utan ekvationssystem

Problemet kan även lösas utan ekvationssystem. (lösning kommer snart i C, antagligen).

Lösning i Java i vilken jag valt att använda mig av lite char-aritmetik istället för att simulera en snurra. Bra att känna till kan vara att versala A-Z motsvaras av talen 65-90 i ASCII-tabellen, så ibland kan man behöva addera 26 (längden av A-Z alfabetet) för att komma tillbaka i intervallet 65-90 t ex för att simulera det faktum att man snurrat runt ett varv (dvs passerat A och hamnat nere i trakterna kring @). Ett problem som dock kan uppstå är att man kan råka glömma det faktum att antalet steg man flyttar medurs utgår ifrån positionen man tidigare snurrat sig fram till och inte grundtillståndet. Detta gör att man måste dra av det totala antalet steg som snurrats/flyttats (och inte bara den "nya" differensen) när man beräknar den egentliga bokstaven genom char-aritmetik snarare än någon form av simulering.

Hur som helst, här nedan följer källkoden. (Och att jag adderar 26 (vid behov) på differensen är för att den kan råka bli negativ, vilket jag inte trivs med.)

import java.util.*;

public class Kryptering
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Krypterad text: ");
		String krypto = scan.next();

		//De tre första bokstäverna.
		char k1 = krypto.charAt(0);
		char k2 = krypto.charAt(1);
		char k3 = krypto.charAt(2);

		// Grund/Start-förskjutningen.
		int start = k1 - 'H';
		if(start<0) start += 26;

		// Grund-differensen.
		int diff = k2 - 'E' - start;
		while(diff<0) diff += 26;

		// Konstanten med vilken differensen ökar.
		int incr = k3 - 'J' - start - 2*diff;
		while(incr<0) incr += 26;

		//Vårt avkodade meddelande.
		String svar = "HEJ";

		//Den totala förskjutningen som skett av snurran (so far).
		int total = start + diff + (diff+incr);

		//Uppdaterar differensen till vad den borde vara, efter
		//det att vi snurrat till oss "HEJ".
		diff += 2*incr;

		//Går igenom det krypterade meddelandet.
		for(int i = 3; i<krypto.length(); i++)
		{
			//Uppdaterar den totala förskjutningen av snurran.
			total += diff;

			//Onödigt att snurra flera varv.
			total %= 26;

			//Snurrar tillbaka till den egentliga bokstaven.
			char add = (char)(krypto.charAt(i) - total);

			//Vi har passerat A och befinner oss nu på något
			//konstigt tecken (typ @ kanske) och bör därför
			//fixa till så att vi hamnar i alfabetet igen.
			if(add<'A') add += 26;

			//Lägger till bokstaven i meddelandet.
			svar += "" + add;

			//Ökar differensen.
			diff += incr;
		}

		//Skriver ut svaret.
		System.out.println("\nMeddelande: " + svar);
	}
}