Kryptografia

Zielony Smok - logo witryny

Generowanie losowego klucza

Liczby generowane przez generatory liczb losowych dostępne w Javie nie są w pełni losowe.

Można ich używać przy prostszych zadaniach. Gdy chcesz np. wygenerować liczbę serialVersionUID, używaną przez mechanizmy serializacji, możesz użyć następującego sposobu:

public static final long serialVersionUID = new Random(
	new GregorianCalendar().getTimeInMillis()).nextLong();

Stworzenie dobrego generatora liczb losowych nie jest uważane za trywialne zajęcie. Od lat biedzą się nad tym doskonali specjaliści. Temat jest tematem – rzeką i jego zgrubne omówienie wymagałoby napisania książki. Postanowiłam zrobić to po swojemu, ale … po mądremu.

Klasy

Klasa Generator.java
package crypto.vigenere;
import java.util.*;
public class Generator{
	public static final long serialVersionUID = new Random(
			new GregorianCalendar().getTimeInMillis()).nextLong();
	private Generator(){}
	public static String[] generuj(int ileLiczb, int ileCyfrKazda,
			FrequencyMap<String> map) throws IllegalArgumentException {
		int podstawa = ileCyfrKazda * ileLiczb * 5;
		ArrayList<String> als = new ArrayList<>();
		for(int i = 0; i < podstawa; i++){
			if(i > (int)(podstawa * 0.9)){
				als.add("9");
			}
			else if(i > (int)(podstawa * 0.8)){
				als.add("8");
			}
			else if(i > (int)(podstawa * 0.7)){
				als.add("7");
			}
			else if(i > (int)(podstawa * 0.6)){
				als.add("6");
			}
			else if(i > (int)(podstawa * 0.5)){
				als.add("5");
			}
			else if(i > (int)(podstawa * 0.4)){
				als.add("4");
			}
			else if(i > (int)(podstawa * 0.3)){
				als.add("3");
			}
			else if(i > (int)(podstawa * 0.2)){
				als.add("2");
			}
			else if(i > (int)(podstawa * 0.1)){
				als.add("1");
			}
			else if(i > 0){
				als.add("0");
			}
		}
		for(int j = 0; j < 10; j++){
			Collections.shuffle(als);
			Collections.rotate(als, (als.size() / 10));
		}
		Random rand = new Random();
		int random;
		String[] strings = new String[ileLiczb];
		for(int j = 0; j < ileLiczb; j++){
			do{
				random = rand.nextInt(als.size() - 2 * ileCyfrKazda - 1);
			}
			while(als.get(random).equals("0"));
			StringBuilder sb = new StringBuilder();
			for(int k = 0; k < ileCyfrKazda; k++){
				map.add(als.get(random + k));
				sb.append(als.remove(random + k));
			}
			strings[j] = sb.toString();
		}
		return strings;
	}
	/**
	 * oblicza frekwencję cyfr 0 do 9 w danej liczbie
	 * @return 11 elementowa tablica intów.
	 * [0] podaje liczbę zer
	 * [1] podaje liczbę jedynek
	 * itd.
	 * [10] liczba cyfr w liczbie (suma [0] do [9])
	 */
	public static int[] stats(String liczba) {
		String str = liczba;
		FrequencyMap<String> fm = new FrequencyMap<>();
		int[] tabl = new int[11];
		for(int i = 0; i < str.length(); i++){
			fm.add(str.substring(i, i + 1));
		}
		for(int j = 0; j < 10; j++){
			tabl[j] = fm.getFrequency(Integer.toString(j));
		}
		tabl[10] = fm.razem();
		return tabl;
	}
}
Klasa Crypto04.java
package crypto.vigenere;
public class Crypto04 {
    public static void main(String[] args) {
        FrequencyMap<String> map = new FrequencyMap<>();
        //generujemy 100 liczb po 200 cyfr
        String[] tab = Generator.generuj(10, 200, map);
        for (String s : tab) {
            System.out.println(s);
        }
        map.printAll();
    }
}

Wyniki

Klasa Generator generuje sekwencję liczb o podanej długości. Do generowania użyłam losowych generatorów Javy oraz metody mieszającej klasy Collection. Jeśli chcesz możesz stworzyć odpowiedni generator losowych sekwencji liter. Pozostawiam to jako ćwiczenie dla Czytelnika.

Po uruchomieniu klasy Crypto04 otrzymujemy na konsoli dziesięć 200-cyfrowych liczb i badamy liczbę poszczególnych cyfr dla wszystkich liczb łącznie.

81296372908300252383600185219713737575647530749931712458811603680764593835851913108819815899447060448403467336201415976032404570393576384737891970966236784016488420799004830677049777198382057768448336
13014633054507408217186843455726935490573317629828098255266368842790613324149605145854740921054096052187821898656884282328941207710970923626925324676489263702041176548738921146012395724558266275094021
91544721385383403592821509326272826111610367150930400313923182184114554339649597206027725644833665392529556853939602451584558339125196810769954181191012282862255414962483870423473958377638544063388358
59602423395704956884258746506738476200963904907281493524631258345669531728371053860423437682655705882619642041702622698267896602560969000589518152860793950461461550144102794980379046104379650994259789
70173885863307087947533210671534026625142392914929490922336201577750402573849553236710405028681953139822586079131401439992000277071802798536250842417166602260119282304909030905162768388895880734901775
72431357394298490595117476530790077005000531056328550021458057116918257691520699244977016277645892157797596713291193987791964750851219427713245149696191706200552989523269730796210764746394233603676268
71861869566643173769096429690137247367803477641916948313126885903079720335856954670121600956078895675433249554109201149118615409479144523689513219690852458274595139385427328185752486684332407050955410
81022286486910041770879804881638883955221046682690296557005978512000695071090357444241215760912047973069147777069118954284951642876763112344055908373593037540917627474001496673425918964773068500374539
78313786063839201401220466344928913601414339722865457391545453345479451324581900265695459548768167469409855238209455978414336065759586526123649716219793715535112809935666645466635232651000846880284691
31940890634186586439566848024848493705182777821482336131463115495320704549693888100198567786022899559202256284742672063047256848879206059412413293079247174362335648279864516219547551173961925610627643

Gdyby cyfry były rozmieszczone losowo każda cyfra występowałaby tak samo często. Jest to warunek konieczny, ale nie wystarczający do losowości. Możliwy byłby układ, że wszystkie np. 100 jedynek występowałoby jedna po drugiej, za nimi 100 dwójek, etc.

Aby zbadać czy cyfry są rzeczywiście rozłożone losowo, konieczne jest zastosowanie testów statystycznych. Takich testów jest mnóstwo. W następnym wpisie pokażemy dwa testy statystyczne, które służą do badania losowości rozkładu.

Aby ocenić czy klucz jest losowy należy użyć testów statystycznych: