2つの一般的な擬似乱数アルゴリズム
2415 ワード
暗号技術では、鍵生成、デジタル署名、アイデンティティ認証、および多くの暗号学プロトコルなど、ランダムシーケンスが非常に重要である.従って、高品質の乱数シーケンスを生成することは、情報のセキュリティに非常に重要な役割を果たす.乱数は真の乱数と偽の乱数に分けられ、コンピュータがアルゴリズムによって生成した乱数は本当の意味での乱数ではなく、解読されやすく、偽の乱数と呼ぶしかない.真の乱数を生成するには,イオン放射イベントを用いたパルス検出器,ガス放電管,漏れ容量など,ハードウェアにより実現しなければならないが,このような装置を1台のコンピュータに搭載することは不可能である.次の2つの一般的なランダムアルゴリズム:線形同余アルゴリズムとRSAアルゴリズム.
1、線形同余
Ni+1=(A*Ni+B)mod i=0,1,...,M-1
要求:B,Mは互いに質量数である;Mのすべての質量因子の積エネルギーはA-1を除去する.Mが4の倍数A-1であれば;A,B,N 0はいずれもMより小さい.A,Bは正の整数(この式によって乱数を出すことができ、興味があれば倒すことができます)
したがって、A=7^5をとる.B=0;M=2^31-1; N 0はシステム時間である.B=0を満たし、M=2^31-1は互いに質量数である.M=2^31-1のすべての質量因子の積エネルギーはA-1=7^5-1を除去する.Mが4の倍数A-1であれば;A,B,N 0はいずれもMより小さい.A,Bは正の整数です.
実装:
RSAは依然として一定の条件を満たす数学の公式に基づいている.
Aは2~(N-1)C=(A EXP D)mod Nから以下の条件を満たすとする:Dは素数であり、Nは2つの素数(P,Q)の積であり、(D*E)mod((P-1)*(Q-1)=1は、C=(A EXP D)mod NがA=(C EXP E)mod Nである場合、CはAに1つずつ対応する;N=15,P=5,Q=3とするとAは2~14の数となる.2~14の擬似乱数を生成します.Dを3、Eを3、
C2=(2EXP3)mod15 = 8,
C3=(3EXP3)mod 15 = 12, C4 = (4EXP3)mod 15= 4, C5 = (5EXP3)mod 15= 5, C6 = (6EXP3)mod 15= 6, C7 = (7EXP3)mod 15= 13, C8 = (8EXP3)mod 15= 2, C9 = (9EXP3)mod 15= 9, C10 = (10EXP3)mod 15= 10, C11 = (11EXP3)mod 15= 11, C12 = (12EXP3)mod 15= 3, C13 = (13EXP3)mod 15= 7, C14 = (14EXP3)mod 15= 14
1、線形同余
Ni+1=(A*Ni+B)mod i=0,1,...,M-1
要求:B,Mは互いに質量数である;Mのすべての質量因子の積エネルギーはA-1を除去する.Mが4の倍数A-1であれば;A,B,N 0はいずれもMより小さい.A,Bは正の整数(この式によって乱数を出すことができ、興味があれば倒すことができます)
したがって、A=7^5をとる.B=0;M=2^31-1; N 0はシステム時間である.B=0を満たし、M=2^31-1は互いに質量数である.M=2^31-1のすべての質量因子の積エネルギーはA-1=7^5-1を除去する.Mが4の倍数A-1であれば;A,B,N 0はいずれもMより小さい.A,Bは正の整数です.
実装:
package org.mino.random;
/**
* @author DingJie
* @date 2014-5-1
* @email [email protected]
*/
public class LineRmainderRandom {
private static long initSeed = System.currentTimeMillis();
/**
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < 100; i++)
{
getRand ();
}
}
private static void getRand ()
{
initSeed = (initSeed * 16807L) % ((1 << 31) - 1);
System.out.println(initSeed);
}
}
実はjava.util.Randomクラスでは、線形同余メソッドが使用されます. protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
、RSA擬似乱数方法RSAは依然として一定の条件を満たす数学の公式に基づいている.
Aは2~(N-1)C=(A EXP D)mod Nから以下の条件を満たすとする:Dは素数であり、Nは2つの素数(P,Q)の積であり、(D*E)mod((P-1)*(Q-1)=1は、C=(A EXP D)mod NがA=(C EXP E)mod Nである場合、CはAに1つずつ対応する;N=15,P=5,Q=3とするとAは2~14の数となる.2~14の擬似乱数を生成します.Dを3、Eを3、
C2=(2EXP3)mod15 = 8,
C3=(3EXP3)mod 15 = 12, C4 = (4EXP3)mod 15= 4, C5 = (5EXP3)mod 15= 5, C6 = (6EXP3)mod 15= 6, C7 = (7EXP3)mod 15= 13, C8 = (8EXP3)mod 15= 2, C9 = (9EXP3)mod 15= 9, C10 = (10EXP3)mod 15= 10, C11 = (11EXP3)mod 15= 11, C12 = (12EXP3)mod 15= 3, C13 = (13EXP3)mod 15= 7, C14 = (14EXP3)mod 15= 14