ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

ŹŪ˰psudo-random generatorPRGȤϡǤʤФʤʤ

  • ʬϤ01Ф꤬ʤȡ
  • ͽ¬Բǽ󤫤龭ͽ¬Ǥʤȡ

λȤ

  • ֤Ϳ줿򸵤˵롣
  • 1Ȥ̿᤬ФȤϥ֡͡ˤ򸵤˷׻򤷤ơη׻̤򵼻ȤƽϤ롣ơεν̿ơʬ֤ѲƤΤǤ롣Ĥޤꡢ֤鵼׻ˡ֤Ѳˡ2ĤΥ르ꥺǤ롣
  • 뤿ˤϡμseedˤȤɬפǤ롣ͤϡ֤뤿Ѥ롣ĤޤꡢͤȤƻȤΤǤ롣Ϥ󥢥åͽ¬ƤϤʤޤ㤨СߤλȤäƤΤȤƤޤȼȤȤǤ롣

Ƽץߥ󥰸졦ץȸˤ뵼

C

rand()

  • stdlib.hѰդƤsrand()˵ΤseedϤȤǤ롣
    • seedȤơtimeؿǼ߻ꤹ뤳Ȥ¿
      • 㡧srand*1;
      • timeؿñ̤֤ͤᡢ롼srand()rand()ȤäƤޤȡ1ô֤ƱͤϤƤޤȤˤʤ롣äơsrand()ϥ롼פγ1ԤФ褤
  • rand()ǵˤ뤳ȤǤ롣
    • ϰϤ0ʾ32768̤Ǥ롣
  • ϰϤʤǵȤ%黻ҤѤ;׻Ѥ礬¿
    • ֵ͡rand() % ϰϤǿ + ϰϤκǾ͡פȤ롣

OpenSSL°BIGNUM饤֥

BIGNUM֥ȤˤBN_rand_range()ؿѤ롣BN_rand_range()ؿν񼰤ϼ̤ꡣ

int BN_rand_range(BIGNUM *result, BIGNUM *range);

δؿΰϼ̤ꡣ

  • result
    • ѤߤBIGNUM֥ȤΥݥ󥿡
    • 줿ǿϤΥ֥Ȥ˳Ǽ롣
  • range
    • 0ǻꤷͤޤǤε롣

ޤBN_generate_prime()ؿȤСǿ뤳ȤǤ롣BN_generate_prime()ؿν񼰤ϼ̤ꡣ

BIGNUM *BN_generate_prime(BIGNUM *ret, int num, int safe, BIGNUM *add, BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg);

δؿΰϼ̤Ǥ롣

  • ret
    • Ƥ줿BIGNUM֥ȡ
      • 줿ǿϤΥ֥Ȥ˳Ǽ롣
    • ˤ⤳Υ֥Ȥ֤롣
    • NULLꤹȡBIGNUM֥Ȥ֤롣
  • num
    • ǿλĤ٤ӥåȿ
  • safe
    • ǿ֤ɤλꤹ롣
      • ǤǿȤ1ơ2dzäƤǿǤΤȤǤ롣
      • 㤨СDH򴹤ǻѤǿϰǿǤɬפ롣
  • add
    • NULLꤵ줿硢줿ǿ򤳤οdzäȤ;remͿ줿ͤ˰פɬפ롣
  • rem
    • addNULLꤵ줿硢줿ǿadddzäȤ;Ϥͤˤʤɬפ롣
    • NULLꤵ줿ϡͤȤ1Ѥ롣
  • callback
    • ǿκݤˡοʹԾ𤵤˻Ѥ륳ХåؿؤΥݥ󥿡
    • NULLꤹХХåʤ
  • cb_arg
    • ʹԾƻ뤹륳Хåؿꤵ줿硢ΰХåؿľϤ롣

RANDLIB

C++

rand()

  • Crand()Ʊ͡

Ruby

Perl

rand

  • rand EXPRפȤ0ʾEXPR̤ε֤
    • EXPRάȡ0ʾ1̤ε֤
  • srandseedǤ롣

Math::Random::MT⥸塼

  • Math::Random::MT⥸塼ȤȤǴñ˥륻̥ĥ뤳ȤǤ롣
  • use Math::Random::MT qw(srand rand);פȤƤСɸrandsrandƱ褦˻Ȥ롣

PHP

rand()

  • rand()ˤ0ʾgetrandmax()̤ε֤
    • WindowsʤɤΤǤgetrandmax()ͤ32768ȤʤäƤ롣
      • 32768礭ߤϡrand()ȤäñǤ롣
  • rand(int min, int max)ȤСϰϤǤ롣
    • ꤷǾͤȺͤޤࡣ
  • srand()ȤСseedǤ롣
  • libcεѤ롣

mt_rand()

  • ɸrand()4ܰʾ®
  • 륻̥ĥѤƵ뤿ᡢ٤Ǥ롣
  • ܾɸrand()δؿ̾ˡmt_פȤƬ줬դƤǤꡢȤƱǤ롣
    • ʤmt_rand()Ѥ硢0ʾmt_getrandmax()̤ͤȤʤ롣

VB.NET

Rnd

  • Rnd()ؿˤꡢ0ʾ1̤ε뤳ȤǤ롣
  • RandomizeơȥȤseedꤹ뤳ȤǤ롣
  • 륢르ꥺ24ӥåƱˡǤ롣

Random饹

  • Random饹ѰդƤޤ
  • 륢르ꥺKnuthθˡǤ롣
  • Random饹Υ󥹥ȥ饯seedǤ롣
    • ̵Υ󥹥ȥ饯ȤȡseedȤEnvironment.TickCountѤ롣
  • Random#Next()ˤ굼(Integer)뤳ȤǤ롣Next()ˤϰĤΤȻʤΤꡢĤΤȤлꤹϰεͤ뤳ȤǤ롣

Dim rnd As New System.Random()
Dim r1 As Integer = rnd.Next(6)			'0ʾ6̤ε롣
MessageBox.Show(r1.ToString())
Dim r2 As Integer = rnd.Next(-10, 10)	'-10ʾ10̤ε롣
MessageBox.Show(r2.ToString())
Dim r3 As Integer = rnd.Next()			'0ʾInt32.MaxValue̤ε롣
MessageBox.Show(r3.ToString())
  • Integerʳε뤿ˡNextBytes()NextDouble()ʤɤ¸ߤ롣

RNGCryptoServiceProvider饹

  • ŹѤε륯饹

Dim random() As Byte = New Byte(100) {}
Dim rng As New System.Security.Cryptography.RNGCryptoServiceProvider()
rng.GetBytes(random)	'100ХĹ롣
  • 0ʳεByteͤϡGetNonZeroBytes()Ȥ

Java

BigInteger

BigIntegerΥ󥹥ȥ饯1ϰϡnꤹȡ02nӥåȤϰϡˡ2Randam󥹥󥹤ꤹȡBigInteger뤳ȤǤ롣

BingInteger int = new BigInteger(int bit , new Random());

ǿϼΤ褦ˤ롣probablePrime()1Miller-Rabinη֤ʤΤǡ㤨1ꤷǿΨ1/2ˤʤ롣

BigInteger primeInt = BigInteger.probablePrime(1, new Random());

Random饹

  • Random饹Ѥƴñ뤳ȤǤ롣
  • 륢르ꥺ48ӥåƱˡǤ롣
  • nextInt()ΰnͿȤϡͤȤ0n-1ϰϤͤȤʤ롣
  • Effective Java٤ι47֥饤֥꡼Τꡢ饤֥꡼ȤפΤȤ˽񤤤Ƥ롣
Random rand = new Random();
System.out.println(rand.nextInt([]));
  • nextInt()ͤηintǤ뤬ͤηȤboolean,long,double,floatǤ᥽åɤѰդƤ롣
᥽å̾ͤηꤷʤȤϰ
nextBoolean()booleantrue or false
nextInt()int-2147483648+2147483647
nextLong()long-9223372036854775808+9223372036854775807
nextDouble()double0.0ʾ1.0̤
nextFloat()float0.0ʾ1.0̤
  • μ(long)ͿȤRandon饹Υ󥹥ȥ饯ꤹ롣뤤Random#setSeed(long)ꤹ뤳ȤǤ롣
Random rand = new Random(seed);

Math.random()

  • 0ʾ1̤doubleε뤿ˤMath.random()¹Ԥ롣
  • seedꤹ뵡ǽʤ

㡧ϰϤε֤᥽å

/**
 * ϰϤε֤.
 * <p>͡ǾͶ˵ϰϤ˴ޤޤ.
 * @param max 
 * @param min Ǿ
 * @return 
 */
private static int getRandom(final int max, final int min) {
	return (int) Math.floor(Math.random() * (max - min + 1)) + min;
}

륹ץ(bash)

RANDOMѿ򻲾ȤǴñ˵뤳ȤǤ롣

$ echo $RANDOM
  • ˡǼǤͤ032767Ǥ롣
  • RANDOMѿ0232-1ȡ뤳ȤǤ롣
  • unsetޥɤRANDOMѿ̵ˤȡΥRANDOMѿθϤϼ

PowerShell

  • Get-RandomޥɥåȤѰդƤ롣
    • 㡧Get-Random 1000פȤС0ʾ1000̤εǤ롣

SQL

SQL Server

  • RAND()ˤ굼01ˤǤ롣
  • RAND()ΰseedǤ롣
  • RAND()ϸƤӽФ뤴Ȥ˰ۤʤ뵼֤
    • 1SELECT֤RAND()ͤƱǤ롣

㡧fooơ֥ʣԤȤSELECTη̤Ϥ٤ƤιԤƱͤˤʤ롣

SELECT RAND() FROM foo;

MySQL

  • RAND()ˤ굼Ǥ롣
  • RAND()ΰseedǤ롣
  • άȡƤӽФ뤴Ȥˡۤʤ뵼֤
    • 1SELECTǤۤʤ뵼֤

PostgreSQL

  • RANDOM()ˤ굼Ǥ롣
  • seedSEEDѿޤSETSEEDؿˤǤ롣
    • seed01ޤǤưǤ롣
  • 1SELECTǤۤʤ뵼֤

Ǥˡ

  • 르ꥺñʣˤǤϲǤʤ
  • ޤûʤäƤޤȤ꤬롣ʣˤΥ르ꥺȤäƿȡ¿ξûûη֤ˤ˴٤äƤޤŹ浻ѤǻȤͽ¬ԲǽǤʤФʤʤΤǡûȤΤϥǤ롣
  • ⤦ҤȤĤηȤơץޡܺ٤Ǥʤ褦ʥ르ꥺϸŵŹΤ褦˥르ꥺ༫ȤƿƤǤꡢΥ르ꥺबŪ˰Ǥ뤫ɤɾǤʤȤȤǤ롣

Ʊˡ

  • 褯ȤƤ뵿Ź浻Ѥ˻ȤȤϤǤʤ
  • R0,R1,ĤȤȤ롣ޤμseedˤ顢η׻ȤäƺǽεR0

R_0~=~(~A~\times~seed~+~C~)~\,~mod~\,~M

ǡA,C,MϡAM,CMפȤ롣

ˡR0顢Τ褦ˤƵR1

R_1~=~(~A~\times~R_0~+~C~)~\,~mod~\,~M

ʹƱͤˤơRnRn+1

R_{n+1}~=~(~A~\times~R_n~+~C~)~\,~mod~\,~M

ĤޤꡢߤεͤAܤCäMdzä;򼡤εȤ櫓ƱˡǤϡǸ֤ͤˤʤȤ롣

  • A,C,Mͤտ򤹤С̵ĵ뤳ȤǤ뤬ͽ¬ԲǽϻʤʤʤСöƱФƤޤȡ˽Ф󤬷֤ФƤƤޤǤ롣줬μȤʤäƤޤm礭ˤмĹʤ뤬ɤĤƱ󤬽ФƤƤޤĤޤꡢƱˡϰŹ浻Ѥ˻Ȥʤ
  • ץߥ󥰸Υ饤֥ؿȤѰդƤ뵿¿ƱˡѤƤ롣㤨СCrandؿJavajava.util.Random饹ʤɤ롣äƤؿѤŹ浻ѤȼȤ롣

ƱˡΥץˤ¸

ƱˡǻȤϼΤ褦ꤷƤ

  • a8dzä5;
  • c
  • m2߾οǡǤ礭ʤ

javaưƱˡΥץSenkeiGoudouHou.javaˤ򼨤

Everything is expanded.Everything is shortened.
  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
 27
 28
 29
 30
 
 
 
 
 
-
|
-
|
|
|
|
|
-
|
|
|
|
-
|
|
|
!
|
-
|
|
!
!
!
/*
 * Ʊˡˤʵ
 * ϡx,a,c,m
 * ϡx=(a*x+c) % mη
 */
public class SenkeiGoudouHou {
 
    public static void main(String[] args) {
        int x=0;    //Ǹ˵᤿ͤ򥻥åȤ롣
        int m=0;    //2߾ο
        int a=8*5+5;    //8dzä5;
        int c=123;    //
        
        try{
            x=Integer.parseInt(args[0]);
            a=Integer.parseInt(args[1]);
            c=Integer.parseInt(args[2]);
            m=Integer.parseInt(args[3]);
        }catch(NumberFormatException e){
            System.out.println("Ʊˡˤ뵼");
            System.out.println("SenkeiGoudouHou <x> <a> <c> <m>");
            return;
        }
        
        for(int i=0;i<20;i++){
            x=(a*x+c)%m;
            System.out.println(x+",\t");
        }
    }
}

嵭ץѤơƱˡμ¸򤷤Ƥߤ롣

>java SenkeiGoudouHou 1 45 123 8
0,	3,	2,	5,	4,	7,	6,	1,
0,	3,	2,	5,	4,	7,	6,	1,
0,	3,	2,	5,

m=8Ȥȡ10ܤ0о줹롣Ĥޤо줷Ƥ롣ºݤˤʹߤƱη֤Ǥ뤳ȤΤ뤳ȤǤ롣

m=4ˤƤߤ롣

>java SenkeiGoudouHou 1 45 123 4
0,	3,	2,	1,
0,	3,	2,	1,
0,	3,	2,	1,
0,	3,	2,	1,
0,	3,	2,	1,

ΤȤ5ܤ0о줷Ƥ롣Τm򾮤ȡûʤäȤ狼ä

Τ褦m礭ƤߤȡϤͤ礭ʤƱ˼Ĺʤ롣ʤȤ20ĤνϤ˼¸ߤƤʤȤ狼롣

>java SenkeiGoudouHou 1 45 123 65536
168,	7683,	18178,	31701,	50412,
40439,	50406,	40169,	38256,	17707,
10506,	14141,	46644,	1951,	22382,
24273,	43832,	6483,	29714,	26533,

ʾιͻꡢְƱʤв٤ǤƱ뤳ȡפȡmϾȤʤȡפ狼롣Ȥܤ16εϤȤ롣Τm=6ȤƤޤȡûʤäƤޤȤ꤬롣ǡm=65,536ʡ216ˤΤ褦礭ͤǵꡢ6dzä;Ф褤ȤǥפĤ

ޤȤȡ0n-1ޤǤϰϤꤿȤˤϡ礭mǵơmod nǹͤϤ򵼻ȤƻȤФ褤ȤȤǤ롣θJavaץSenkeiGoudouHou2.javaˤ򼡤˼

Everything is expanded.Everything is shortened.
  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
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 
 
 
 
 
-
|
|
|
|
|
|
-
|
|
|
|
|
|
!
|
|
-
|
|
-
-
|
-
|
|
|
!
!
|
|
-
|
|
!
!
!
/*
 * Ʊˡˤ뵼0n-1ε
 * ϡn
 * ϡ0n-120Ĥ
 */
public class SenkeiGoudouHou2 {
    //饹ѿ
    static int x=1;    //Ǹ˵᤿ͤ򥻥åȤ롣
    
    //ؿ
    //nn-1ޤǤ
    //͡᤿
    static int MyRandom(int n){
        int m=65536;
        int a=8*5+5;
        int c=123;
        x=(a*x+c)%m;
        int r=x%n;
        return r;
    }
    
    //main
    public static void main(String[] args) {
        int n=10000;    //ϰϡꤵʤС줬ǥեͤꤵ롣
        
        if(args.length==1){
            try{
                n=Integer.parseInt(args[0]);
            }catch(NumberFormatException e){
                System.out.println("Ʊˡˤ뵼ɽ0n-1ε");
                System.out.println("SenkeiGoudouHou2 <n> nϰ");
                return;
            }
        }
        
        //20ĺäɽ
        for(int i=0;i<20;i++){
            int r=MyRandom(n);
            System.out.println(r+",\t");
        }
    }
}

42ꤷȤξϼΤ褦ˤʤ롣

>java SenkeiGoudouHou2 2
0,	1,	0,	1,
0,	1,	0,	1,
0,	1,	0,	1,
0,	1,	0,	1,
0,	1,	0,	1,

>java SenkeiGoudouHou2 4
0,	3,	2,	1,
0,	3,	2,	1,
0,	3,	2,	1,
0,	3,	2,	1,
0,	3,	2,	1,

m65,536ʤΤǡĹϤ2,4ξϤ줾2,4ȤʤäƤޤäƤ롣ʤʤСƱˡˤϡ̤η夬ǤϤʤʤȤ꤬ƤޤΤǤ롣ǤʤΤ򤵤ndzä;ϤǤʤʤ롣㤨Сn=4ǡ6XXä;ȡ6004dzڤ뤫顢XX;η׻˻ȤΤǤ롣
ˤϡ̤ηܤФ褤ʤʤС̤ηϥǤ롣̤ηȤˤϡx2dzäƤn2ܤ⾮ʤä顢;褦ˤФ褤嵭ץSenkeiGoudouHou2.javaо줷MyRandom᥽åɤ򼡤Τ褦ѹФ褤

	static int MyRandom(int n){
		int m=65536;
		int a=8*5+5;
		int c=123;
		x=(a*x+c)%m;
		int r=x;

		//rn2ܤ礭ַ֤
		while(r >= n*2){
			//r2dz
			r /= 2;
		}
		//rndzä;ͤ
		r %= n;

		return r;
	}

νMyRandom᥽åɤѹץSenkeiGoudouHou3.javaˤϼ̤Ǥ롣

>java SenkeiGoudouHou3 4
1,	3,	0,	3,	2,	0,
2,	0,	0,	0,	1,	2,
1,	3,	1,	1,	1,	2,
3,	2,

ϥåؿȤˡ

ϥåؿȤäơͽ¬Բǽäʶˤ뵿郎롣

ɥС꡼εͽ¬뤿ˤϡߤΥ󥿡ͤΤɬפ롣󥿡ͤΤ뤿ˤϡϥåؿΰˤʤФʤʤΤǤ롣϶ˤƺʤΤǡɥС꡼ϼεͽ¬ǤʤĤޤꡢεϡϥåؿΰͽ¬Բǽ٤Ƥ롣

륻̡ĥȤˡ

MȤˡ

ŹȤˡ

  • ŹȤ뵿뤳ȤǤ롣
  • ΤȤΰŹAESΤ褦оݰŹǤäƤ⡢RSAŹΤ褦ʸŹǤäƤ褤
  • ɥС꡼εͽ¬뤿ˤϡߤΥ󥿡ͤΤɬפ롣ޤǤ˽Ϥ줿ϡŹʸΤǡ󥿡ͤΤȤΤϡŹɤ뤳Ȥ¾ʤʤ϶ˤƺʤΤǡɥС꡼ϼεͽ¬ǤʤĤޤꡢεǤϰŹε̩ͽ¬Բǽ٤Ƥ뤳Ȥˤʤ롣
  • ŹȤäζŪʤΤȤơANSI X9.17ANSI X9.31Appendix˵ҤƤˡ롣ϰŹ楽եȥPGPǤȤƤ롣

Ф륢å

  • ̤ˤϰŹФ륢åαƤ˱ơ¸ߤϤޤռʤӤϸȤפܤäƤΤǡɥС꡼ιоݤȤʤ䤹

seed

  • μϡŹθɤŨġ
  • μ郎ɥС꡼ΤƤޤСε郎뵿Ϥ٤ƥɥС꡼Τ줿ȤˤʤʵǻȤƤ륢르ꥺϡԤΤƤ뤳ȤꤹˡäơμϥɥС꡼̩ˤʤФʤʤ
  • 򥢥ɥС꡼Τʤ褦ˤ뤿ˤϡƸԲǽĿΤˤ뤳ȤǤ롣

סФ륢å

  • ɬפˤʤäȤˤξǿФΤǤϤʤסȸƤФե˥ʥӥåߤƤˡ롣Ź楽եȥμɬפȤϡΥס뤫ɬפʤΥΥӥåФƻȤ
  • ⤷ɥС꡼ˤΥסƤΤƤޤȡμͽ¬Ƥޤǽ롣

PRGοŪ

one-way functionPRG

[]
one-way function¸ߤ
͡length-tripling pseudo random generatorPRGˤ¸ߤ

[]
G=~\{~G_k~:~\{~0,1~\}^k~\to~\{~0,1~\}^{3k}~\}_{k~\in~\mathbb{N}}PRG
def\forall~D~\(~PPT~\,~distinguisher~\)~|~Pr~[~x~\overset{$}{\leftarrow}~\{~0,1~\}^{3k}~:~D~\(~x~\)~=1~]~-~Pr~[~s~\overset{$}{\leftarrow}~\{~0,1~\}^k~;~x=G_k~\(~s~\)~:~D~\(~x~\)~=1~]~|:neg

ȡΩġ

U_{3k}~\approx~G~\(~U_k~\)

ǡUkkӥåȥȥ󥰤ΰʬ̣ۤ롣

α

ŹǤȤ롣㤨Сξ̤ǻȤ롣

  • ̸ŹϤ̩
  • ŹϤǥ̾ˤǡ
  • ȥ꡼Ź

ʸ

  • غǿŹ浻ѡ
  • EclipseˤθؽJavaǤϤ륢르ꥺ


*1 unsigned) time(NULL