Взлом алгоритма Эль-Гамаль( с помощью алгоритма Шенкса)

Данное задание мне выдавали по предмету криптология. Наверно один из немногих предметов, который мне кажется реально полезным и интересным.

Реализовывал на Java т.к боялся что числа выйдут за пределы стандартных типов данных, а в Java для этого есть удобный тип данных BigInteger. Такто.

Итак условие:
В следующих задачах зашифрован алгоритмом ЭльГамала текст, написанный на английском языке. Использован следующий алфавит:
"A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z| |,|.|".
Блок "подсказки" расположен в начале криптотекста и является общим для всех его блоков. Его длина считается неизвестной. Найти секретный ключ и расшифровать текст.

"5148154611033774886049492438294008383372872853501067660147906401592062201450665781876473"

Открытый ключ: p=89981741 g=2 h=76976449

Часть первая - решение задачи целочисленного логарифмирования ( поиск секретного ключа a)
На вход подаётся p,g,h

package Shenks;

import java.math.BigInteger;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map.Entry;

public final class Program {

/**
* @param args
*/
public static void main(String[] args) {

if(args.length==3)
{
// TODO Auto-generated method stub
System.out.println("y=a^x(mod n) x-?");

System.out.println("y= "+args[0]);
BigInteger y=new BigInteger(args[0]);

System.out.println("a= "+args[1]);
BigInteger a=new BigInteger(args[1]);


System.out.println("n= "+args[2]);
Integer n=new Integer(args[2]);

Shanks(y, a, n);

}else
{
System.out.println("Expecting 3 arguments to run");
}
}

public static int Shanks(BigInteger y,BigInteger a,int n)
{

Hashtable babySteps=new Hashtable();
Hashtable giantSteps=new Hashtable();
// TODO: Prepare
int result=0;

int s=(int)Math.floor((( Math.sqrt(n))));

BigInteger N=BigInteger.valueOf(n);

System.out.print("s=");
System.out.println(s);



// TODO: Do baby step
System.out.println("Starting baby steps,baby!:)");
BigInteger temp=y;
for(int i=0;i {
BigInteger value=temp.mod(N);
babySteps.put(i, value);
temp=temp.multiply(a);
//System.out.println(
// String.format("%d\\%d %s", i,s,value.toString()));
}


// TODO: Do Giant steps
System.out.println("Starting giant steps,oh my god!!!:)");
// temp=a;
// temp=temp.pow(s);
// BigInteger temp2=temp;
for(int i=0;i {
//System.out.println(temp2.toString());
temp=a.modPow(BigInteger.valueOf(s*(i+1)), N);
//BigInteger value=temp;
giantSteps.put((i+1)*s,temp);

//temp2=temp2.multiply(temp);
//System.out.println(
// String.format("%d\\%d %s", i,s,temp.toString()));
}

//TODO:Check giant and baby
System.out.println("Comparing giant steps and baby steps");

Iterator> set1=babySteps.entrySet().iterator();

Boolean loop=true;
int loopN=0;
while(set1.hasNext()&& loop)
{
Entry entry1=set1.next();
Iterator> set2=giantSteps.entrySet().iterator();
//System.out.println(
// String.format("Loop %d\\%d", loopN,s)
//);
while(set2.hasNext() && loop)
{

Entry entry2=set2.next();
//BigInteger value1=entry1.getValue();
//BigInteger value2=entry2.getValue();
//System.out.println(
// String.format("%s - %s", value1,value2));
if(entry1.getValue().equals(entry2.getValue()))
{
System.out.print("Entry found:");
//System.out.println(
//String.format("r=%d st=%d", entry1.getKey(),entry2.getKey()));
result=entry2.getKey()-entry1.getKey();
System.out.println(result);
loop=false;
}
}
loopN++;
}


//TODO:Testing
System.out.print("Test:");
if(y.equals(a.modPow(BigInteger.valueOf(result),BigInteger.valueOf(n))))
System.out.println("OK");

return result;
}
}

Часть вторая - дешифрация
На вход подаётся найденный пароль, Р, с1, и остальные ci
c1 - это первые 8 цифр из зашифрованного сообщения.

package Shenks;

import java.math.BigInteger;

public final class Decrypt {

public static String Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ ,.";

/**
* @param args
*/
public static void main(String[] args) {
System.out.println(
String.format("Pass:%s", args[0]) );

System.out.println(
String.format("c1:%s", args[2]) );



System.out.println(
String.format("P:%s", args[1]) );


Integer pass=new Integer(args[0]);

BigInteger p=new BigInteger(args[1]);

BigInteger c1=new BigInteger(args[2]);

for(int i=3;i System.out.println(
String.format("ci:%s", args[i]) );

System.out.println("==DECRYPTION==");
for(int i=3;i {
BigInteger c2=new BigInteger(args[i]);
BigInteger m=DecryptGamal(pass,c1,c2,p);
String msg=GetMessage(m.intValue());
System.out.print(msg);
}
}

private static String GetMessage(Integer m) {
Integer val=m;
String result="";
for(int i=0;i<4 br="" i=""> {
int index=val%100;
result=Decrypt.Alphabet.charAt(index)+result;
val=val/100;
}
return result;
}

private static BigInteger DecryptGamal(Integer pass, BigInteger c1,BigInteger c2, BigInteger p) {
BigInteger bigpass=p.subtract(
BigInteger.valueOf((long)(pass+1)));

BigInteger c1pow=c1.modPow(bigpass, p);

BigInteger result=((c2.mod(p)).multiply(c1pow)).mod(p);

return result;
}
}

Нахождение разшифрованного сообщения оставляю в качестве бонуса :D