Appel constructeur BigInteger (java.Math.BigInteger)

**charles_dg** · 18/05/2011, 15h54

Bonjour,

Je sais pas si vous avez déjà rencontré ce problème mais je génère de grands nombres premiers aléatoires grâce à la classe BigInteger.

Cependant, le premier appel (que ce soit un grand ou un petit nombre) a généré prend énormément de temps. En l’occurrence ici 5 sec pour un nombre aléatoire de 2 bit!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
BigInteger m;
long start;
long end;
long time=0;
 
SecureRandom rand = SecureRandom.getInstance("SHA1PRNG");
start = System.currentTimeMillis();
m = new BigInteger(1, rand);
end = System.currentTimeMillis();
System.out.println("random number generation time was " + (end - start) + " ms.");
 
for(int i = 1; i <= 10; i++){
	m = null;
 
	start = System.currentTimeMillis();
 
	m = new BigInteger(512, Integer.MAX_VALUE ,rand);
 
	end = System.currentTimeMillis();
 
	time += (end-start);
	System.out.println("random number " + i + " generation time was " + (end - start)+ " ms.");
 
	}
System.out.println("random number generation time was " + time + " ms. Average = " + (time/10) + " ms");

Voici les résultats

random number generation time was 5003 ms.
random number 1 generation time was 118 ms.
random number 2 generation time was 88 ms.
random number 3 generation time was 145 ms.
random number 4 generation time was 93 ms.
random number 5 generation time was 179 ms.
random number 6 generation time was 491 ms.
random number 7 generation time was 87 ms.
random number 8 generation time was 65 ms.
random number 9 generation time was 49 ms.
random number 10 generation time was 385 ms.
random number generation time was 1700 ms. Average = 170 ms

Aucune idée?

merci d'avance

**Logan Mauzaize** · 18/05/2011, 16h13

Je dirais que c'est l'initialisation de ton "randomiser" qui prend du temps.

D'après Wikipedia :

Une méthode courante pour générer de l'aléa en cryptographie consiste à « accumuler de l'entropie » (via diverses sources disponibles sur un ordinateur : temps entre deux accès au disque, taille de la mémoire, mouvements du pointeur de la souris...) et à faire passer le résultat dans une fonction de hachage cryptographique comme MD5 ou SHA-1. Ce principe est utilisé par Yarrow et Fortuna qui ne génèrent un nombre que lorsque l'entropie est suffisante.

**tchize_** · 18/05/2011, 16h27

C'est mon avis aussi, tu commence au 10ème à manque d'entropie et il faut du temps pour que ton système en génère correctement. Par exemple ici, pendant que j'écrit ce message, j'ai lancé la commande "dd if=/dev/random of=/dev/null" sous linux. Sur 30 secondes approximativement de fonctionnement, elle a pu générer 120 octets de hasard entropique, pas énorme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
$ dd if=/dev/random of=/dev/null bs=1
^C120+0 enregistrements lus
120+0 enregistrements écrits
120 octets (120 B) copiés, 28,3403 s, 0,0 kB/s

**tchize_** · 18/05/2011, 16h32

edit: je viens de tester ton code, j'obtiens ce genre de résultat

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
random number 496 generation time was 42 ms.
random number 497 generation time was 140 ms.
random number 498 generation time was 26 ms.
random number 499 generation time was 26 ms.
random number 500 generation time was 21 ms.
random number 501 generation time was 38 ms.
random number 502 generation time was 38 ms.
random number 503 generation time was 27 ms.
random number 504 generation time was 79 ms.
random number 505 generation time was 48 ms.
random number 506 generation time was 67 ms.
random number 507 generation time was 16 ms.
random number 508 generation time was 16 ms.
random number 509 generation time was 18 ms.
random number 510 generation time was 27 ms.
random number 511 generation time was 138 ms.

La javadoc ne parle pas d'utiliser l'entropie. Par contre, les restrictions sur l'output peuvent impliquer des calculs plus ou moins long, ce qui expliquerait les variations de temps.

**tchize_** · 18/05/2011, 16h39

visiblement, je lit pas tout, c'est ton premier nombre qui est lent. Pas de comportement similaire ici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
random number generation time was 27 ms.
random number 1 generation time was 453 ms.
random number 2 generation time was 51 ms.
random number 3 generation time was 25 ms.
random number 4 generation time was 25 ms.

Par contre le premier appel est "jsute aléatoire" et les suivant sont des "probablement premiers", ce qui n'est pas la meme chose. Je pencherais plutot sur le temps d'initialisation de ton générateur aléatoire.

**charles_dg** · 18/05/2011, 16h41

Envoyé par tchize_

edit: je viens de tester ton code, j'obtiens ce genre de résultat

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
random number 496 generation time was 42 ms.
random number 497 generation time was 140 ms.
random number 498 generation time was 26 ms.
random number 499 generation time was 26 ms.
random number 500 generation time was 21 ms.
random number 501 generation time was 38 ms.
random number 502 generation time was 38 ms.
random number 503 generation time was 27 ms.
random number 504 generation time was 79 ms.
random number 505 generation time was 48 ms.
random number 506 generation time was 67 ms.
random number 507 generation time was 16 ms.
random number 508 generation time was 16 ms.
random number 509 generation time was 18 ms.
random number 510 generation time was 27 ms.
random number 511 generation time was 138 ms.

La javadoc ne parle pas d'utiliser l'entropie. Par contre, les restrictions sur l'output peuvent impliquer des calculs plus ou moins long, ce qui expliquerait les variations de temps.

Ok, tu as aussi le premier nombre à générer qui te prend plusieurs secondes? La je regarde dans SecureRandom, si la méthode setSeed(byte[] seed) peut m'aider à contourner ce problème de temps.

Par contre ton exécution est bien plus rapide que la mienne. Du à de la programmation sur javacard, j'ai du installer windows en dualboot (bootcamp) sur mon portable mac.

**charles_dg** · 18/05/2011, 16h42

Envoyé par tchize_

visiblement, je lit pas tout, c'est ton premier nombre qui est lent. Pas de comportement similaire ici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
random number generation time was 27 ms.
random number 1 generation time was 453 ms.
random number 2 generation time was 51 ms.
random number 3 generation time was 25 ms.
random number 4 generation time was 25 ms.

Par contre le premier appel est "jsute aléatoire" et les suivant sont des "probablement premiers", ce qui n'est pas la meme chose. Je pencherais plutot sur le temps d'initialisation de ton générateur aléatoire.

5 sec. me semble énorme chez moi pour l'initialisation d'un générateur non?

**tchize_** · 18/05/2011, 16h42

une javacard est loin d'etre aussi puissante qu'un CPU, attendez vous à ce que le générateur soit lent

Pour le reste voir nos messages qui se sont croisés

**Logan Mauzaize** · 18/05/2011, 16h43

L'implémentation par défaut semble être sun.security.provider.SecureRandom.

D'après une doc (je suppose plus ou moins officielle) :

Note that if a seed is not provided, we attempt to provide sufficient seed bytes to completely randomize the internal state of the generator (20 bytes). However, our seed generation algorithm has not been thoroughly studied or widely deployed.

This empty constructor automatically seeds the generator. We attempt to provide sufficient seed bytes to completely randomize the internal state of the generator (20 bytes). Note, however, that our seed generation algorithm has not been thoroughly studied or widely deployed.

The first time this constructor is called in a given Virtual Machine, it may take several seconds of CPU time to seed the generator, depending on the underlying hardware. Successive calls run quickly because they rely on the same (internal) pseudo-random number generator for their seed bits.

source

**tchize_** · 18/05/2011, 16h44

Envoyé par charles_dg

5 sec. me semble énorme chez moi pour l'initialisation d'un générateur non?

Regardez le temps que met

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 rnd.nextBytes(new byte[1])

sur un générateur tout neuf. A mon avis c'est l'auto seeding qui prend du temps. Vous pourriez seeder vous même, mais ça vous prendrais aussi du temps pour gérer un seed fiable....

**charles_dg** · 18/05/2011, 16h45

Envoyé par tchize_

une javacard est loin d'etre aussi puissante qu'un CPU, attendez vous à ce que le générateur soit lent

Non mais la c'est du coté Client, et donc aucune interaction avec la carte pour le moment.

**charles_dg** · 18/05/2011, 16h49

Envoyé par tchize_

Regardez le temps que met

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 rnd.nextBytes(new byte[1])

sur un générateur tout neuf. A mon avis c'est l'auto seeding qui prend du temps. Vous pourriez seeder vous même, mais ça vous prendrais aussi du temps pour gérer un seed fiable....

random next byte generation time was 5025 ms.

Donc 5 sec aussi... Chez vous?

**Logan Mauzaize** · 18/05/2011, 17h04

Pas du tout

source:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package com.developpez.nemek;
 
import java.security.SecureRandom;
 
public class D1082665 {
	public static void main(String[] args) throws Exception {
		for (int i = 0; i < 20; i++) {
			long start = System.currentTimeMillis();
			SecureRandom rand = SecureRandom.getInstance("SHA1PRNG");
			System.out.println(i + ") Secure random getInstance " + (System.currentTimeMillis() - start) + "ms");
			start = System.currentTimeMillis();
			rand.nextBytes(new byte[1]);
			System.out.println(i + ") Secure random nextBytes " + (System.currentTimeMillis() - start) + "ms");
		}
	}
}

output:

0) Secure random getInstance 15ms
0) Secure random nextBytes 78ms
1) Secure random getInstance 0ms
1) Secure random nextBytes 0ms
2) Secure random getInstance 0ms
2) Secure random nextBytes 0ms
3) Secure random getInstance 0ms
3) Secure random nextBytes 0ms
4) Secure random getInstance 0ms
4) Secure random nextBytes 0ms
5) Secure random getInstance 0ms
5) Secure random nextBytes 0ms
6) Secure random getInstance 0ms
6) Secure random nextBytes 0ms
7) Secure random getInstance 0ms
7) Secure random nextBytes 0ms
8) Secure random getInstance 0ms
8) Secure random nextBytes 0ms
9) Secure random getInstance 0ms
9) Secure random nextBytes 0ms
10) Secure random getInstance 0ms
10) Secure random nextBytes 0ms
11) Secure random getInstance 0ms
11) Secure random nextBytes 0ms
12) Secure random getInstance 0ms
12) Secure random nextBytes 0ms
13) Secure random getInstance 16ms
13) Secure random nextBytes 0ms
14) Secure random getInstance 0ms
14) Secure random nextBytes 0ms
15) Secure random getInstance 0ms
15) Secure random nextBytes 0ms
16) Secure random getInstance 0ms
16) Secure random nextBytes 0ms
17) Secure random getInstance 0ms
17) Secure random nextBytes 0ms
18) Secure random getInstance 0ms
18) Secure random nextBytes 0ms
19) Secure random getInstance 0ms
19) Secure random nextBytes 0ms

**charles_dg** · 18/05/2011, 17h16

J'ai lancé ton code, le résultat est tjs le même pr moi pr le premier nextBytes:

0) Secure random getInstance 11ms
0) Secure random nextBytes 5027ms
1) Secure random getInstance 0ms
1) Secure random nextBytes 0ms
2) Secure random getInstance 0ms
2) Secure random nextBytes 0ms
3) Secure random getInstance 0ms
3) Secure random nextBytes 0ms
4) Secure random getInstance 0ms
4) Secure random nextBytes 0ms
5) Secure random getInstance 0ms
5) Secure random nextBytes 1ms
6) Secure random getInstance 0ms
6) Secure random nextBytes 0ms
7) Secure random getInstance 0ms
7) Secure random nextBytes 0ms
8) Secure random getInstance 0ms
8) Secure random nextBytes 0ms
9) Secure random getInstance 0ms
9) Secure random nextBytes 0ms
10) Secure random getInstance 0ms
10) Secure random nextBytes 0ms
11) Secure random getInstance 0ms
11) Secure random nextBytes 0ms
12) Secure random getInstance 1ms
12) Secure random nextBytes 0ms
13) Secure random getInstance 0ms
13) Secure random nextBytes 0ms
14) Secure random getInstance 0ms
14) Secure random nextBytes 0ms
15) Secure random getInstance 1ms
15) Secure random nextBytes 1ms
16) Secure random getInstance 0ms
16) Secure random nextBytes 0ms
17) Secure random getInstance 0ms
17) Secure random nextBytes 0ms
18) Secure random getInstance 0ms
18) Secure random nextBytes 0ms
19) Secure random getInstance 0ms
19) Secure random nextBytes 0ms

**tchize_** · 18/05/2011, 18h29

vérifiez que vous n'avez pas ajouté des providers supplémentaires dans votre installation java, donc l'un d'entre eux serait extrèmement peu performant. Quelle est la class de l"implémentation retournée (getClass().getName())

**charles_dg** · 18/05/2011, 19h20

Envoyé par tchize_

vérifiez que vous n'avez pas ajouté des providers supplémentaires dans votre installation java, donc l'un d'entre eux serait extrèmement peu performant. Quelle est la class de l"implémentation retournée (getClass().getName())

Où est-ce-que je verifie les providers? et comment utiliser (getClass().getName())?

Merci

**tchize_** · 18/05/2011, 19h58

sur l'instance retournée, faites un getClass().getName() et affichez le résultat. On saura quel provider vous avez et on pourra comparer avec ceux qui n'ont pas de soucis de perfs

**charles_dg** · 18/05/2011, 20h07

Envoyé par tchize_

sur l'instance retournée, faites un getClass().getName() et affichez le résultat. On saura quel provider vous avez et on pourra comparer avec ceux qui n'ont pas de soucis de perfs

Euh donc je le fais sur l'instance de SecureRandom, c'est ça?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
SecureRandom rand = SecureRandom.getInstance("SHA1PRNG");
System.out.println(rand.getClass().getName());

J'obtiens:

java.security.SecureRandom

**tchize_** · 18/05/2011, 22h19

Effectivement pas très utile, j'aurais cru que getInstance retournerais des isntances générées par le provider

**charles_dg** · 18/05/2011, 23h21

Héhé ok.

Penses-tu que si je réinstalle le jdk et Eclipse, ça pourrait aider?

Appel constructeur BigInteger (java.Math.BigInteger)

API standards et tierces Java

Discussions similaires

Partager

Partager