当前位置：文档之家 › Pseudorandom Number Generation Based on Controllable Cellular Automata”, Special issue Adv

Pseudorandom Number Generation Based on Controllable Cellular Automata”, Special issue Adv

  • 格式：pdf
  • 大小：245.89 KB
  • 文档页数：15

Future Generation Computer Systems20(2004)627–641Pseudorandom number generation based oncontrollable cellular automataSheng-Uei Guan∗,Shu ZhangDepartment of Electrical and Computer Engineering,National University of Singapore,10Kent Ridge Crescents,Singapore119260,SingaporeAbstractA novel cellular automata(CA)—controllable CA(CCA)is proposed in this paper.Further,CCA are applied in pseudo-random number generation.Randomness test results on CCA pseudorandom number generators(PRNGs)show that they are better than one-dimensional(1D)CA PRNGs and can be comparable to two-dimensional(2D)ones.But they do not lose the structure simplicity of1D CA.Further,we develop several different types of CCA PRNGs.Based on the comparison of the randomness of different CCA PRNGs,wefind that their properties are decided by the actions of the controllable cells and their neighbors.These novel CCA may be applied in other applications where structure non-uniformity or asymmetry is desired.©2003Elsevier B.V.All rights reserved.Keywords:Cellular automata;Randomness test;Pseudorandom number generator;Controllable;Hybrid1.IntroductionA central problem in any stream cipher scheme is to generate long,unpredictable key sequences.Since real random numbers can be obtained from some physi-cal phenomena only,they are difficult to be employed in real applications.Hence,pseudorandom numbers generated by artificial design patterns have to be used instead.One commonly used type of pseudorandom number generators(PRNGs)is based on cellular au-tomata(CA).CA was initiated in the early1950s as a general framework for modeling complex structures capable of self-reproduction and self-repair[15].∗Corresponding author.Tel.:+65-6874-5153;fax:+65-6779-1103.E-mail addresses:eleguans@.sg,engp9594@.sg (S.-U.Guan),dudushu@(S.Zhang).In1986,Wolfram[18]first applied CA in pseudo-random number generation.The intensive interest in thisfield can be attributed to the phenomenal growth of the VLSI technology that permits cost-effective re-alization of the simple structure of local-neighborhood CA.Wolfram’s work in[18]proved that the random-ness of the patterns generated by maximum-length CA is significantly better than other widely used methods, such as linear feedback shift registers(LFSRs).In the last decade,one-dimensional(1D)CA PRNGs have been extensively studied[2,5,6,7–9,11–14,16,17].Recent interest is more focused on two-dimensional(2D)CA PRNGs[3,10]since it seems that their randomness is much better than that of1D CA PRNGs.But taking into account the design complexity and computation efficiency,it is quite difficult to conclude which one is pared to2D CA PRNGs,1D PRNGs are easier to be im-plemented in a large scale.In this paper,we propose0167-739X/$–see front matter©2003Elsevier B.V.All rights reserved. doi:10.1016/S0167-739X(03)00128-6628S.-U.Guan,S.Zhang/Future Generation Computer Systems20(2004)627–641a family of novel CA PRNGs that obtain the same randomness as that of2D CA PRNGs without losing the structure simplicity of1D CA PRNGs.In the following,wefirst give an overview on CA and CA PRNGs in Section2.Then in Section3, we present the definition and properties of a set of novel CA PRNGs—controllable CA(CCA)PRNGs. Section4compares CCA PRNGs to1D and2D CA PRNGs.Section5delineates a set of CCA PRNGs and compares their properties.Finally,we end the paper with a short discussion and conclusion in Section6.2.Related work2.1.Introduction to randomness testsReal random numbers can only be obtained from some physical phenomenon.The random numbers generated by PRNGs are not truly random,but only pseudorandom.Although this assertion is inevitable, we would still like to obtain sequences that behave as if they were random.Thus,the problem is how to decide whether the sequences are random enough? Statistical(empirical)test could be a good solution in this respect.If a sequence passed a number of quantitative tests,we could assert that the sequence is random.But we should also note that there are no guarantees,only predictions in numerical practice are possible.Following,we introduce two widely used randomness test suites—ENT test and DIEHARD. The former is designed according to the criteria set by Knuth[1]and the latter is devised by Marsaglia [4].Detailed introduction to these two tests is given in Appendixes A and B.2.2.CA backgroundA cellular automaton is an array of cells where each cell is in any one of its permissible states.At each discrete time step(clock cycle)the evolution of a cell depends on its transition rule(the combi-natorial logic),which is a function of the present states of its k neighbors for a k-neighborhood CA. The cellular array(grid)is n-dimensional,where n=1,2,3is used in practice.We define the state of a CA at time t to be the n-tuple formed from the states of the individual cells,x(t)=[x1(t),...,x n(t)].The next-state function of a3-neighborhood(r=1)CA is computed as x(t+1)=f(x(t))=[f1 (0,x1(t),x2(t)),...,f i(x i−1(t),x i(t),x i+1(t)),...]. When each f i is a linear function,f is also a linearfunction,mapping n-tuples to n-tuples.The evolutionof the i th cell in a1D,3-neighborhood CA can berepresented as a function of the present states of the(i−1)th,(i)th,and(i+1)th cells as x i(t+1)= f i(x i−1(t),x i(t),x i+1(t)),where f i represents the tran-sition rule for the(i)th cell.Some definitions used extensively to characterizethe properties of CA are noted below.Definition1.If the rules of a CA cell involve onlyXOR logic,then it is called a linear rule.Rules in-volving XNOR logic are referred to as complementedrules.A CA with all the cells having linear rules iscalled a linear CA,whereas a CA having a combina-tion of XOR and XNOR rules is called an additive CA. Definition2.If all the CA cells obey the same rule, then the CA is said to be a uniform CA;otherwise,it is a non-uniform CA.Definition3.A CA is said to be a periodic boundaryCA(PBCA)if the extreme cells are adjacent to eachother.A CA is said to be an intermediate boundaryCA(IBCA)if the next state of the left(right)most celldepends on itself,its right(left)neighbor,and the onenext to(before)it.A CA is said to be a null-boundaryCA if the extreme cells are only connected to its left(right)cell.Programmable CA(PCA)is initially mentioned in[17].It is a non-uniform CA that allows different rulesto be used at different time steps on the same cell.Compared to uniform CA,PCA allows several controllines per cell.Through these control lines,differentfunctions(rules)can be applied to the same cell at dif-ferent time steps according to the rule control signals.Fig.1shows an additive PCA cell structure.Applyingsuch a cell structure to each cell in an N-cell PCA,all the possible additive non-complemented rule com-binations can be achieved to realize any non-uniformadditive PCA.Such an N-cell PCA can implement8Ndifferent CA configurations.Generally,transition rule is one of the critical fac-tors that decide the property of CA,whether it is uni-S.-U.Guan,S.Zhang/Future Generation Computer Systems20(2004)627–641629Fig.1.An additive PCA cell structure.form CA or PCA.Since there is a lot of work done to explore the properties of different rules,we only use those rules that have been proved to be good in random number generations in our work.Here we give the Boolean form of these rules and their num-bers are given in accordance with Wolfram’s conven-tion:Rule30:x i(t+1)=x i−1(t)XOR(x i(t)OR x i+1(t)). Rule90:x i(t+1)=x i−1(t)XOR x i+1(t).Rule150:x i(t+1)=x i−1(t)XOR x i(t)XOR x i+1(t). Rule165:x i(t+1)=x i−1(t)XNOR x i+1(t). Rule105:x i(t+1)=x i(t)XNOR(x i−1(t)XOR x i+1(t)).2.3.Cellular automata pseudorandom number generatorsIn this section,we discuss several1D and2D CA PRNGs proposed since the last decade.Before we pro-ceed to introduce the generators,wefirst investigate what properties of CA will affect the randomness of the sequences generated by CA PRNGs.In general,there are four aspects of CA configura-tion affecting the randomness:•Boundary conditions—null boundary or periodic boundary:generally periodic boundary condition is better than null boundary condition in random num-ber generation.•Length of a CA—the total number of cells in a CA:a CA formed from N cells with a single rule generally has a cycle length much shorter than2N−1.As the length of the CA increases the maximum possible cycle length of the pseudorandom sequence increases.•Initial seed—the initial state configuration in CA: generally,the effect of initial seed on randomness is trivial.To counteract its effect,in the follow-ing work,we apply the randomness test on a set of randomly generated initial seeds instead of only one.Transition rule—obviously,the randomness of the sequences generated by different rules varies a lot.2.3.1.1D CA PRNGsRule-30uniform CA has been extensively studied by Wolfram in1986[18].It is thefirst time that scientists applied CA in random number generation. Wolfram’s work on rule-30CA demonstrated its abil-ity to produce highly random,temporal bit sequences [19].Wolfram also suggested that rule-30CA can be efficiently implemented in parallel.A study in[13] shows that in rule-30CA,the correlation dies out and a bit stream3–4cells away is no longer correlated. Therefore,the auto-and cross-correlation of a rule-30 CA is less than that of a parallel LFSR ter, other rules are also applied in uniform CA PRNGs. Tomassini et al.concluded in[9]that according to the DIEHARD test results,rule105is the best RNG,fol-lowed by rules165,90and150,with rule30coming last.Following the idea of uniform CA PRNGs,more researchers focus their interest on non-uniform CA PRNGs since non-uniform CA PRNGs are better than uniform ones in general.Thefirst non-uniform CA PRNG was proposed by Hortensius et al.in1989 [12].This non-uniform CA uses rules90and150. This CA PRNG is referred to hence as PCA90–150. Surprisingly,the combination of these two simple linear rules yields maximum-length cycles.Unlike uniform rule-30CA,adjacent cells in non-uniform CA are not correlated in both time and space[12]. However,the binary sequences produced by some cells in a non-uniform CA fail some random num-ber tests because of distribution problems.Another non-uniform CA PRNG which uses the combination of rules30and45was also proposed by Hortensius et al.[13].This generator can evolve to a random pattern of outputs,but its bit sequence correlation is much higher than that of the PCA90–150[13]. Later in1996,Sipper and Tomassini[11]evolved a 50-cell CA with a mélange of rules90,150and165. This CA is referred to henceforth as PCA90–165.630S.-U.Guan,S.Zhang /Future Generation Computer Systems 20(2004)627–641Based on their work,Tomassini et al.[9]evolved an-other 50-cell CA with the rule combination 90,165,150and 105in 1999.This CA is referred to hence-forth as PCA 90–105.These two CA are evolved using cellular programming evolution algorithm while those two CA proposed by Hortensius are hand-crafted.The DIEHARD test results show that these two non-uniform CA PRNGs are better than those designed by Hortensius et al.in [12,13].But they still cannot pass some of the tests in DIEHARD and are inferior to the classical generators.2.3.2.2D CA PRNGsWork on 1D CA PRNGs not only shows the suitabil-ity of CA in random number generation but also raises another question:is it possible to further improve the randomness of CA PRNGs?Chowdhury et al.[3]de-scribed a methodology for producing pseudorandom numbers by 2D CA in 1994.Their results suggest that 2D CA are superior to 1D ones of the same size in pseudorandom number generation.Following his idea,Tomassini et al.evolved several 8×82D CA PRNGs with rule 15,63,31and 47.DIEDARD test results show that some of the evolved CA PRNGs can pass all the tests in DIEHARD.And based on the observation of these evolved 2D CA PRNGs,they can handcraft even better PRNGs.Although 2D CA PRNGs are better than 1D CA PRNGs in random number generation,they lose the structure simplicity and computation efficiency of 1D CA PRNGs.Therefore,how to find a set of CA PRNGs which not only can pass all the DIEHARD test but also have the merit of 1D CA PRNGs becomesanFig.2.A controllable cell structure.important problem.Under this motivation,we propose a novel CA in the next A PRNGs 3.1.Controllable CAFollowing the idea of PCA in which a rule control line is added into each cell to improve the random-ness of CA PRNGs,we add more control lines on CA cells to control the neighborhood relation and up-dating of states to further improve the randomness of 1D CA PRNGs.This results in a new type of CA—controllable CA or CCA.In this section,the structure and properties of CCA are presented.To explain the scheme explicitly,several new concepts are defined first to identify the CCA properties.Definition 4.A CCA is a CA in which some cells can be controlled via cell control signals.Definition 5.If a cell is under the control of a cell control signal,it is a controllable cell ,otherwise it is a basic cell .CCA is the combination of controllable cells and basic cells.Both controllable cells and basic cells could have rule control signals.Fig.2shows the non-programmable/programmable controllable cell structure.In this paper,we will discuss programmable controllable cells only.The status of a controllable cell refers to how its state will be computed in the current time step.It isS.-U.Guan,S.Zhang/Future Generation Computer Systems20(2004)627–641631Fig.3.The structure of a CCA.decided by its current cell control signal.The status of a controllable cell can be active or inactive.If the state of a controllable cell is computed as usual(only according to the current rule control signals and the states of its neighbors),it is an active cell and the states of its neighbors are computed as usual too.If the state of a controllable cell is not updated(its state will remain stable or be complemented)in the current time step,it is an inactive cell.The inactive controllable cell is referred to henceforth as an idle cell.How the states of its neighbors will be computed is decided by certain rules.And these rules decide the property of CCA.The structure of a CCA is shown in Fig.3.All the cells in a CCA have rule control lines while only those controllable cells(i.e.cell#i and cell#j)have cell control pared to a PCA in the same size, CCA has several more cell control lines.The number of cell control lines is the same as that of controllable cells in CCA.In our work,the rule(or cell)control signals are generated by a rule(or cell)control CA. In the next sub-section,we will present several basic CCA PRNGs and discuss their properties.Random-ness tests show that CCA PRNGs are good in random number generation.The usage of controllable cells in CCA differenti-ates itself from PCA in which only rule control signals exist.Once the actions of controllable cells and basic cells are specified,the setting of controllable cells will decide the performance of CCA.The common idea in PCA and CCA is that they both use some control lines on the CA cells to make the CA transition more un-predictable andflexible.The difference is that in PCA all the cells have uniform structures while obviously in CCA the structure of controllable cells are not the same as that of basic cells.3.2.Basic CCA PRNGsThe simplest example we can easily think of is that when a controllable cell is inactive,it keeps its lat-est state and the states of its neighbors are computed as usual.In this way,the controllable cell will affect the state computation of its neighbors during the cur-rent time step in the same way as the previous time step.This model is referred to as CCA0.Note that the 1bit memory of the inactive controllable cell is some-how wasted as we do not change its content,we can have a variation:when the controllable cell is inactive, its state is complemented.This model is referred to as CCA1.These two models are quite easy to be im-plemented in hardware and we even canfind a PCA to simulate each.We may wonder that if so,what is the difference between a CCA0(or CCA1)PRNG and PCA PRNG.To answer this question,we design the following randomness test on CA PRNGs.The ENT test is used to evaluate the randomness of CA PRNGs. Thefinal result is a real number that is referred to henceforth as randomness value.This value is calcu-lated based on the test results of entropy,Serial cor-relation coefficient(SCC)and chi-square test using a function F:F=(entropy−6)×20%+(1−|SCC|)×20% +f(chi-square)×60%f(chi-square)=0if chi-square>90%or<10%,1if10%<chi-square<90% The reason why we adjust the original test values is to ensure that thefinal randomness value falls into [0,1]and a higher value represents better random-ness.The objective of this test is to compare not only632S.-U.Guan,S.Zhang /Future Generation Computer Systems 20(2004)627–641the randomness of CCA PRNGs and PCA PRNGs but also the randomness of controllable cells and basic cells.CA PRNGs generate random number se-quence as following:each cell generates a random bit sequence.In each time step,the state of a cell is recorded.A cell’s randomness value is the ENT test result on the sequence it generated.This test isparison of PCA/CCA0/CCA1/CCA2(L =16bit,M =800cycles).The definition of CCA2is in Fig.5.peated 100times with 100randomly generated initial seeds (for rule control CA and cell control CA,tested CA).The average randomness value is recorded as the final result and the variance of these 100tests are recorded in the meantime.In all the figures presented in this paper,the randomness value is the average value.Fig.4shows the test result on CCA PRNGsS.-U.Guan,S.Zhang/Future Generation Computer Systems20(2004)627–641633and PCA90–150PRNGs.L is the length of CA,M the number of cycles CA runs through.The tested CCA0and CCA1both have only one controllable cell(cell8).The rule combination and rule control signals for PCA,CCA0and CCA1are identical.As shown in Fig.4(a),all the PCA cells ob-tain a randomness value of about0.68.The basic cells in CCA0have a randomness value about0.84while the controllable cell gets a much lower value which is nearly the same as that of PCA cells.Note that CCA0 and CCA1get similar test result,we can derive that the ‘complement’action of a controllable cell is not use-ful to improve its randomness in this case.Although the randomness of a controllable cell is much worse than that of a basic cell,it improves the overall ran-domness of CCA0and CCA1.Referring to Fig.4(b), we can see that the variance of CCA0and CCA1cells, whether they are basic cells or controllable cells,is much lower than that of PCA cells.It means that the controllable cell can also improve the overall perfor-mance stability of CCA0and CCA1PRNGs.The shortcoming of CCA0and CCA1is that the randomness of controllable cells is much worse than that of basic cells.To solve this problem,we design an-other CCA—where the neighbors of a controllable cell will bypass it when it is inactive.That means the inac-tive controllable cell would not be involved in the state computation of its neighbors.In this way,the neigh-borhood relationship is dynamically changed during the CA computation process.This type of CCA is re-ferred to henceforth as CCA2or neighbor-changing CA(NCA).Note that CCA2cannot be simulated by a PCA due to its neighbor-changing behavior.The ran-domness test result of CCA2PRNG is also shown in Fig.4.We can see that for CCA2,the randomness of a controllable cell is similar to that of a basic cell. Till now,all the random number sequences are sequentially generated by one cell of CA PRNGs. But generally CA PRNGs generate pseudorandom numbers in parallel.To evaluate the randomness of parallel CCA PRNGs,we design the following test. All the tested CA PRNGs have a length of16.For each generator,an8bit integer is generated as the output random number during each time step.Each CA PRNG runs M cycles to generate a sequence of M random numbers.This sequence is evaluated with the ENT test.For each CA PRNG,this test is repeated 100times with100randomly generated initial seeds.Table1ENT test results of PCA/CCA0/CCA1/CCA2PRNGsChi-square(pass rate)(%)Entropy(average value)SCC(average value)PCA90–15070 6.1012100.121479CCA0100 6.2412100.049906CCA1100 6.2687580.040313CCA2100 6.4238560.008055The pass rate in the chi-square test is the percentage of tests whose chi-square test result is between10and 90%.The entropy and SCC value are the arithmetic mean of all the100tests.Table1shows the test re-sults on PCA,CCA0,CCA1and CCA2PRNGs.All the CCA PRNGs can pass the chi-square test at100% while PCA PRNGs get a much lower pass rate of 70%.CCA2gets the highest entropy and SCC value among all the tested CA PRNGs.Therefore,we can say that CCA2PRNG is the best among them.Since CCA0and CCA1get similar results in all the follow-ing tests,we will only discuss CCA0in the following work to represent both of them.In the next section, we compare the randomness of CCA0/CCA2PRNGs with that of1D PCA PRNGs and2D CA PRNGs.A PRNGs vs.1D/2D CA PRNGsA0PRNGs vs.1D CA PRNGsWe have shown in the last section that according to the ENT test results,CCA PRNGs are better than PCA 90–150PRNGs.To confirm this,we use a more com-plete test suite—DIEHARD in the following work. The tests in DIEHARD require a large binaryfile of random integers to be tested.In our work,all the ran-dom number sequences generated by CA PRNGs are 10M bytes.Table2shows the DIEHARD test results on PCA90–150and CCA PRNGs.The lengths of all the tested PRNGs arefixed as64cells.The rule com-bination,rule control signals and cell control signals are identical for all tested CA PRNGs.Rule combi-nation is90and150.Rule control CA uses rule105. Cell control CA uses rule165.In CCA PRNGs,the controllable cells are averagely distributed among ba-sic cells.Site(cell)spacing and time spacing are used in PCA and CCA PRNGs to remove correlation.The634S.-U.Guan,S.Zhang/Future Generation Computer Systems20(2004)627–641Table2DIEHARD test result on PCA/CCA0(L=64;P=32/16/8bit integer;p1:averagely interleaving;ss:site spacing;ts:time spacing;ccn: number of controllable cells;count the ones1:count the ones for specific bytes;count the ones2:count the ones for a stream of bytes) No.Test name P=32,ss=1,ts=0P=16,ss=2,ts=0P=8,ss=3,ts=0P=16,ss=2,ts=1PCA 90–150CCA0/CCA2,ccn=8PCA90–150CCA0/CCA2,ccn=8PCA90–150CCA0/CCA2,ccn=8PCA90–150CCA0/CCA2,ccn=81Overlapping sum Pass Pass Pass Pass Pass Pass Pass Pass 2Runs up1Pass Pass Pass Pass Pass Pass Pass Pass Runs Down1Pass Pass Pass Pass Pass Pass Pass Pass Runs up2Pass Pass Pass Pass Pass Pass Pass Pass Runs Down2Pass Pass Pass Pass Pass Pass Pass Pass 33D sphere Pass Pass Pass Pass Pass Pass Pass Pass 4A parking lot Fail Pass Fail Pass Fail Pass Fail Pass 5Birthday Spacing Pass Pass Pass Pass Pass Pass Pass Pass 6Count the ones1Fail Fail Pass Pass Pass Pass Pass Pass 7Binary rank6×8Fail Fail Pass Pass Pass Pass Pass Pass 8Binary rank31×31Pass Pass Pass Pass Pass Pass Pass Pass 9Binary rank32×32Pass Pass Pass Pass Pass Pass Pass Pass 10Count the ones2Pass Pass Pass Pass Pass Pass Pass Pass 11Bitstream test Pass Pass Pass Pass Pass Pass Pass Pass 12Craps wins Fail Pass Fail Pass Pass Pass Pass Pass Throws Pass Pass Pass Pass Pass Pass Pass Pass 13Minimum distance Pass Pass Pass Pass Fail Pass Pass Pass 14Overlapping Perm.Fail Fail Pass Pass Fail Pass Pass Pass 15Squeeze Pass Pass Pass Pass Pass Pass Pass Pass 16OPSO test Pass Pass Pass Pass Fail Fail Pass Pass 17OQSO test Fail Fail Fail Fail Fail Fail Pass Pass 18DNA test Pass Pass Pass Pass Pass Pass Pass Pass Number of tests passed1214151713161718site spacing parameter ss is the number of sites be-tween outputs in CA.The time spacing parameter ts is the number of time steps between output numbers. Wefirst test the CA PRNGs without time spacing. Tofind a suitable site spacing parameter,we tested different values:ss=1,2or3.Referring to Table2, we can see that when ss=2,both CCA0and PCA 90–150PRNGs get the best results.But they still can-not pass all the tests in DIEHARD.Tomassini et al.[9] suggested in that time spacing is crucial to generate a very high quality random number sequence.Our test results are in accordance with his suggestion.With a time spacing of1,CCA0PRNGs can pass all the tests in DIEHARD.Since under all the circumstance,CCA0 PRNGs pass more tests than PCA90–150PRNGs,we can conclude with confidence that CCA0is better than PCA90–150in random number generation.In[9],Tomassini et al.showed the DIEHARD test results of PCA90–165and PCA90–105(in their work,these two CA are referred to as Sipper and Tomassini,and Tomassini et al.,respectively). Table3shows the test results of their CA PRNGs and ours.Without time spacing,both PCA90–165 and PCA90–105PRNGs fail at leastfive tests while CCA0/CCA2PRNGs only fail one test.With a time spacing of2,both PCA and CCA0/CCA2PRNGs can pass13tests while they did not provide the test results on the otherfive tests.Hence,we can conclude here that CCA0/CCA2PRNGs are comparable to or better than PCA90–105and PCA90–165PRNGs. Considering that CCA use more control lines than PCA,we may suspect that whether we can further improve PCA’s random quality with more control lines?Two bit PCA PRNGs,which use two control lines per programmable cell,may be a good example to be compared with CCA PRNGs.In a2bit PCA, four rules are available for each cell during CA com-putation.Here,rules90,150,165and105are chosen. Table4presents the DIEHARD test results of PCA 90–150,CCA0,CCA2and2bit PCA with50cells.ItS.-U.Guan,S.Zhang/Future Generation Computer Systems20(2004)627–641635 Table3DIEHARD test results of PCA90–105/PCA90–165/CCA0/CCA2PRNGs(L=50cells)No.Test name L=50,ts=0,ss=2L=50,ts=1,ss=2CCA0/CCA2PCA90–165PCA90–105CCA0/CCA2PCA90–165PCA90–105 1Overlapping sum Pass Pass Pass Pass Pass Pass2Runs up1Pass Pass Pass Pass Pass Pass Runs Down1Pass Pass Pass Pass Pass PassRuns up2Pass Pass Pass Pass Pass PassRuns Down2Pass Pass Pass Pass Pass Pass33D sphere Pass Pass Pass Pass Pass Pass4A parking lot Pass Pass Pass Pass Pass Pass5Birthday Spacing Pass Fail Fail Pass Pass Pass6Count the ones1Pass Fail Fail Pass Pass Pass7Binary rank6×8Pass Pass Pass Pass Pass Pass8Binary rank31×31Pass Fail Fail Pass Pass Pass9Binary rank32×32Pass Fail Fail Pass Pass Pass10Count the ones2Pass Pass11Bitstream test Pass Pass12Craps wins Pass Pass Pass Pass Pass Pass Throws Pass Pass Pass Pass Pass Pass13Minimum distance Pass Fail Fail Pass Pass Pass14Overlapping Permu Fail Pass Pass Pass Pass Pass15Squeeze Pass Pass Pass Pass Pass Pass16OPSO test Pass Pass17OQSO test Pass Pass18DNA test Pass PassNumber of tests passed1788181313shows that with a time spacing of1and site spacing of2,both CCA0/CCA2and2bit PCA PRNGs can pass all the tests in DIEHARD while PCA90–150 PRNGs fail one test.Table4also presents the DIEHARD test results of CA PRNGs where L=16and32.Since the length of CA is critical to its randomness,we can say that a CA with less than32cells cannot generate good random number sequences.Under all the circum-stance,CCA0/CCA2PRNGs get better randomness than PCA90–150PRNGs.When the length of CA is32,CCA0/CCA2PRNGs can pass one more test than2bit PCA PRNGs.Further we apply the ENT test on CCA0,CCA2and2bit PCA PRNGs.The test results are shown in Table5.All of them can pass the chi-square test at100%.In the SCC and entropy test, CCA2PRNG gets better result than2bit PCA and CCA0gets similar result as2bit PCA.To examine the behavior of PCA90–150,CCA0 and2bit PCA,we present the2D time–space diagram as shown in Fig.5.Each generator has50cells and runs200time steps.The x-axis is from cell1to50;the y-axis is from time step0to200(from top to bottom).Obviously,PCA90–150has some patterns A0,CCA2and2bit PCA have no such patterns in their diagrams.Fig.6shows the randomness value of each cell in a2bit PCA PRNG where the randomness value func-tion is defined as in Section3.2.The results show that a2bit PCA PRNG gets similar result as CCA2PRNG and slightly better result than CCA0PRNG.Accord-ing to the DIEHARD/ENT/randomness value test re-sults and the time–space diagram,we can conclude that CCA2is better than2bit PCA and2bit PCA is comparable to CCA0in random number generation. While considering the high wiring cost of2bit PCA, it is hard to say which one is better between CCA0 and2bit PCA PRNGs.A PRNG vs.2D CA PRNGWe have introduced in Section2.3that Tomassini et al.evolved several2D CA PRNGs.In[10],they showed that some of the evolved8×82D CA PRNGs。

合集下载

03+分组密码—3DES及分组密码工作模式

03+分组密码—3DES及分组密码工作模式

➢ characteristics of the seed
secure if known adversary can determine output so must be random or pseudorandom number27
Linear Congruential Generator
➢ properly designed, can be as secure as a block cipher with same size key
➢ but usually simpler & faster
34
RC4
➢ a proprietary cipher owned by RSA DSI ➢ another Ron Rivest design, simple but effective ➢ variable key size, byte-oriented stream cipher ➢ widely used (web SSL/TLS, wireless WEP/WPA) ➢ key forms random permutation of all 8-bit values ➢ uses that permutation to scramble input info
可并行 可与计算 可随机访问 可证明安全 加解密相似
明文不满一个 字，则丢尾巴
不用填充
Copyright by © 王鲲鹏
工作模式 反馈特征
CBC
CFB
Copyright by © 王鲲鹏
OFB
CRT
存储加密的特征和要求
1. 攻击者可随意获取密文 2. 明文密文的大小一样 3. 分组单位互相独立，可单独访问 4. 加密以16字节的分组为单位 5. 除数据分组外，无其他元数据 6. 不同地方的相同明文加密后得到不同密
securerandom.getinstance的取代方法 -回复

securerandom.getinstance的取代方法 -回复

securerandom.getinstance的取代方法-回复Title: Alternative Methods to SecureRandom.GetInstanceIntroduction:In modern cryptography, securing random number generation is essential for cryptographic operations, such as key generation, initialization vectors, and nonces. One such popular method used in many programming languages is SecureRandom.GetInstance. However, recent concerns regarding vulnerabilities in this method have led to the development of alternative techniques. In this article, we will delve into the issues surrounding SecureRandom.GetInstance and explore some viable replacements.1. Understanding SecureRandom.GetInstance: SecureRandom.GetInstance is a method that provides a cryptographically strong pseudorandom number generator (CSPRNG). It allows developers to access a secure and unpredictable stream of random numbers. It is widely used in both public and private key cryptography algorithms due to its reputation for providing high-quality random numbers.2. Vulnerabilities in SecureRandom.GetInstance:Despite its widespread use, SecureRandom.GetInstance has faced scrutiny due to potential vulnerabilities. In 2013, the revelation of the NSA's Bullrun program raised concerns about possible backdoors in cryptographic algorithms. While no concrete evidence existed, doubts were raised about the integrity of SecureRandom.GetInstance in generating random numbers. Additionally, implementation flaws in certain versions of Java have been discovered, resulting in the generation of predictable random numbers.3. Alternative Methods:To address the concerns surrounding SecureRandom.GetInstance, several alternative methods have emerged. These alternatives focus on improving random number generation and ensuring cryptographic strength.a) java.security.SecureRandom:The java.security.SecureRandom class is an alternative to SecureRandom.GetInstance that provides enhanced security. It utilizes a platform-specific native implementation, making it less susceptible to potential vulnerabilities in the underlying Java implementation. The java.security.SecureRandom class followsstandards set by the National Institute of Standards and Technology (NIST) in generating random numbers.b) CryptGenRandom (Windows):For Windows-based applications, CryptGenRandom is an alternative to SecureRandom.GetInstance. It is a cryptographic service provider in the Windows operating system that generates random numbers using hardware and software entropy sources. CryptGenRandom is well-integrated into the Windows cryptographic infrastructure, making it a reliable choice.c) /dev/random and /dev/urandom (Unix-based systems):Unix-based systems offer alternatives toSecureRandom.GetInstance through the use of /dev/random and /dev/urandom devices. These devices provide access to random numbers based on environmental noise and other system events. /dev/random provides cryptographically secure random numbers at the cost of blocking when not enough entropy is available, while /dev/urandom sacrifices blocking for faster random number generation.4. Implementation Examples:To illustrate the usage of alternative methods, let's consider some code examples:a) java.security.SecureRandom:SecureRandom srng = new java.security.SecureRandom();b) CryptGenRandom (Windows):byte[] randomBytes = new byte[16];CryptGenRandom(CRYPT_PROVIDER, randomBytes, randomBytes.length);c) /dev/random and /dev/urandom (Unix-based systems): OpenSSL library in C/C++: RAND_bytes(buffer, length);Conclusion:Secure random number generation is a critical aspect of cryptographic operations. While SecureRandom.GetInstance has traditionally been a popular method, concerns regarding its security have necessitated the exploration of alternative solutions. The alternatives discussed in this article, includingjava.security.SecureRandom, CryptGenRandom, and /dev/randomand /dev/urandom, offer improved security and reliability for generating random numbers. Developers must choose an appropriate alternative based on their specific platform and cryptographic requirements.。

基于非线性效应的光学逻辑门研究

基于非线性效应的光学逻辑门研究

基于非线性效应的光学逻辑门研究惠战强【摘要】光逻辑门是未来全光网络中光信息处理的核心元件,它可以实现高速光包交换,全光地址识别,数据编码,奇偶校验,信号再生等功能.介绍了几种基于非线性效应的全光逻辑门,分析了它们的系统结构和工作原理,并对各自的特点进行了比较,指出光逻辑门在未来的发展方向及应用领域.【期刊名称】《现代电子技术》【年(卷),期】2008(031)015【总页数】3页(P152-154)【关键词】半导体光放大器;太赫兹光非时称解复用器;马赫-曾得干涉仪;超快非线性干涉仪【作者】惠战强【作者单位】西安邮电学院,陕西,西安,710061【正文语种】中文【中图分类】TN929.1全光逻辑门是实现全光信号处理的核心元件，它可以实现全光信号提取，全光地址识别，全光复用/解复用以及全光开关等[1-4]，因此，在未来的全光高速通信网络和新一代光计算机中将有着巨大的应用潜力，目前，国内外均对此展开了广泛深入的研究。

半导体光放大器以其体积小，光谱性能好，工作波长范围宽，响应时间短以及良好的非线性特性等优点，成为各种全光逻辑门中的主要功能器件，本文介绍了几种基于半导体光放大器中的非线性光学效应工作的全光逻辑门，并对其各自的特点进行了比较。

1 实现光学逻辑门的非线性光学原理实现全光逻辑门主要是基于半导体光放大器中的交叉增益调制波长转换原理，在忽略放大的自发辐射引起的载流子消耗的条件下，波长的转换过程可以用以下两个方程描述[5,6]:(1)(2)其中，N是有源区中载流子浓度，I是注入电流大小，e是电子电量，V是有源区体积，Γ是模场限制因子，A是有源区横截面积，h是普朗克常数，c是真空中光速，下标S，c分别对应信号光和探测光，gi(N,vi)是对应光波的增益系数，v是光波的频率，和分别对应正向和反向传播的光功率，αint是有源区内部的损耗系数，R(N)是非辐射复合和自发辐射复合引起的载流子消耗。

为准确模拟载流子沿半导体光放大器有源区长度方向的分布，可以采用分段模型进行数值模拟。

rfc4187.Extensible Authentication Protocol Method for 3rd Generation Authentication and Key Agreemen

rfc4187.Extensible Authentication Protocol Method for 3rd Generation Authentication and Key Agreemen

Network Working Group J. Arkko Request for Comments: 4187 Ericsson Category: Informational H. Haverinen Nokia January 2006 Extensible Authentication Protocol Method for 3rd GenerationAuthentication and Key Agreement (EAP-AKA)Status of This MemoThis memo provides information for the Internet community. It doesnot specify an Internet standard of any kind. Distribution of thismemo is unlimited.Copyright NoticeCopyright (C) The Internet Society (2006).IESG NoteThe EAP-AKA protocol was developed by 3GPP. The documentation ofEAP-AKA is provided as information to the Internet community. While the EAP WG has verified that EAP-AKA is compatible with EAP asdefined in RFC 3748, no other review has been done, includingvalidation of the security claims. The IETF has also not reviewedthe security of the underlying UMTS AKA algorithms.AbstractThis document specifies an Extensible Authentication Protocol (EAP)mechanism for authentication and session key distribution that usesthe Authentication and Key Agreement (AKA) mechanism. AKA is used in the 3rd generation mobile networks Universal MobileTelecommunications System (UMTS) and CDMA2000. AKA is based onsymmetric keys, and typically runs in a Subscriber Identity Module,which is a UMTS Subscriber Identity Module, USIM, or a (Removable)User Identity Module, (R)UIM, similar to a smart card.EAP-AKA includes optional identity privacy support, optional resultindications, and an optional fast re-authentication procedure.Arkko & Haverinen Informational [Page 1]Table of Contents1. Introduction and Motivation (4)2. Terms and Conventions Used in This Document (5)3. Protocol Overview (9)4. Operation (15)4.1. Identity Management (15)4.1.1. Format, Generation, and Usage of Peer Identities (15)4.1.2. Communicating the Peer Identity to the Server (21)4.1.3. Choice of Identity for the EAP-Response/Identity (23)4.1.4. Server Operation in the Beginning ofEAP-AKA Exchange (23)4.1.5. Processing of EAP-Request/AKA-Identity bythe Peer (24)4.1.6. Attacks against Identity Privacy (25)4.1.7. Processing of AT_IDENTITY by the Server (26)4.2. Message Sequence Examples (Informative) (27)4.2.1. Usage of AT_ANY_ID_REQ (27)4.2.2. Fall Back on Full Authentication (28)4.2.3. Requesting the Permanent Identity 1 (29)4.2.4. Requesting the Permanent Identity 2 (30)4.2.5. Three EAP/AKA-Identity Round Trips (30)5. Fast Re-Authentication (32)5.1. General (32)5.2. Comparison to AKA (33)5.3. Fast Re-Authentication Identity (33)5.4. Fast Re-Authentication Procedure (35)5.5. Fast Re-Authentication Procedure when Counter isToo Small (37)6. EAP-AKA Notifications (38)6.1. General (38)6.2. Result Indications (39)6.3. Error Cases (40)6.3.1. Peer Operation (41)6.3.2. Server Operation (41)6.3.3. EAP-Failure (42)6.3.4. EAP-Success (42)7. Key Generation (43)8. Message Format and Protocol Extensibility (45)8.1. Message Format (45)8.2. Protocol Extensibility (47)9. Messages (48)9.1. EAP-Request/AKA-Identity (48)9.2. EAP-Response/AKA-Identity (48)9.3. EAP-Request/AKA-Challenge (49)9.4. EAP-Response/AKA-Challenge (49)9.5. EAP-Response/AKA-Authentication-Reject (50)9.6. EAP-Response/AKA-Synchronization-Failure (50)Arkko & Haverinen Informational [Page 2]9.7. EAP-Request/AKA-Reauthentication (50)9.8. EAP-Response/AKA-Reauthentication (51)9.9. EAP-Response/AKA-Client-Error (52)9.10. EAP-Request/AKA-Notification (52)9.11. EAP-Response/AKA-Notification (52)10. Attributes (53)10.1. Table of Attributes (53)10.2. AT_PERMANENT_ID_REQ (54)10.3. AT_ANY_ID_REQ (54)10.4. AT_FULLAUTH_ID_REQ (54)10.5. AT_IDENTITY (55)10.6. AT_RAND (55)10.7. AT_AUTN (56)10.8. AT_RES (56)10.9. AT_AUTS (57)10.10. AT_NEXT_PSEUDONYM (57)10.11. AT_NEXT_REAUTH_ID (58)10.12. AT_IV, AT_ENCR_DATA, and AT_PADDING (58)10.13. AT_CHECKCODE (60)10.14. AT_RESULT_IND (62)10.15. AT_MAC (63)10.16. AT_COUNTER (64)10.17. AT_COUNTER_TOO_SMALL (64)10.18. AT_NONCE_S (65)10.19. AT_NOTIFICATION (65)10.20. AT_CLIENT_ERROR_CODE (66)11. IANA and Protocol Numbering Considerations (66)12. Security Considerations (68)12.1. Identity Protection (69)12.2. Mutual Authentication (69)12.3. Flooding the Authentication Centre (69)12.4. Key Derivation (70)12.5. Brute-Force and Dictionary Attacks (70)12.6. Protection, Replay Protection, and Confidentiality (70)12.7. Negotiation Attacks (71)12.8. Protected Result Indications (72)12.9. Man-in-the-Middle Attacks (72)12.10. Generating Random Numbers (73)13. Security Claims (73)14. Acknowledgements and Contributions (74)15. References (74)15.1. Normative References (74)15.2. Informative References (76)Appendix A. Pseudo-Random Number Generator (77)Arkko & Haverinen Informational [Page 3]1. Introduction and MotivationThis document specifies an Extensible Authentication Protocol (EAP)mechanism for authentication and session key distribution that usesthe 3rd generation Authentication and Key Agreement mechanism,specified for Universal Mobile Telecommunications System (UMTS) in[TS33.102] and for CDMA2000 in [S.S0055-A]. UMTS and CDMA2000 areglobal 3rd generation mobile network standards that use the same AKA mechanism.2nd generation mobile networks and 3rd generation mobile networks use different authentication and key agreement mechanisms. The GlobalSystem for Mobile communications (GSM) is a 2nd generation mobilenetwork standard, and EAP-SIM [EAP-SIM] specifies an EAP mechanismthat is based on the GSM authentication and key agreement primitives. AKA is based on challenge-response mechanisms and symmetriccryptography. AKA typically runs in a UMTS Subscriber IdentityModule (USIM) or a CDMA2000 (Removable) User Identity Module((R)UIM). In this document, both modules are referred to as identity modules. Compared to the 2nd generation mechanisms such as GSM AKA, the 3rd generation AKA provides substantially longer key lengths and mutual authentication.The introduction of AKA inside EAP allows several new applications.These include the following:o The use of the AKA also as a secure PPP authentication method indevices that already contain an identity module.o The use of the 3rd generation mobile network authenticationinfrastructure in the context of wireless LANso Relying on AKA and the existing infrastructure in a seamless waywith any other technology that can use EAP.AKA works in the following manner:o The identity module and the home environment have agreed on asecret key beforehand. (The "home environment" refers to the home operator’s authentication network infrastructure.)o The actual authentication process starts by having the homeenvironment produce an authentication vector, based on the secret key and a sequence number. The authentication vector contains arandom part RAND, an authenticator part AUTN used forauthenticating the network to the identity module, an expectedresult part XRES, a 128-bit session key for integrity check IK,and a 128-bit session key for encryption CK.Arkko & Haverinen Informational [Page 4]o The RAND and the AUTN are delivered to the identity module.o The identity module verifies the AUTN, again based on the secretkey and the sequence number. If this process is successful (theAUTN is valid and the sequence number used to generate AUTN iswithin the correct range), the identity module produces anauthentication result RES and sends it to the home environment.o The home environment verifies the correct result from the identity module. If the result is correct, IK and CK can be used toprotect further communications between the identity module and the home environment.When verifying AUTN, the identity module may detect that the sequence number the network uses is not within the correct range. In thiscase, the identity module calculates a sequence numbersynchronization parameter AUTS and sends it to the network. AKAauthentication may then be retried with a new authentication vectorgenerated using the synchronized sequence number.For a specification of the AKA mechanisms and how the cryptographicvalues AUTN, RES, IK, CK and AUTS are calculated, see [TS33.102] for UMTS and [S.S0055-A] for CDMA2000.In EAP-AKA, the EAP server node obtains the authentication vectors,compares RES and XRES, and uses CK and IK in key derivation.In the 3rd generation mobile networks, AKA is used for both radionetwork authentication and IP multimedia service authenticationpurposes. Different user identities and formats are used for these; the radio network uses the International Mobile Subscriber Identifier (IMSI), whereas the IP multimedia service uses the Network AccessIdentifier (NAI) [RFC4282].2. Terms and Conventions Used in This DocumentThe key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].The terms and abbreviations "authenticator", "backend authentication server", "EAP server", "peer", "Silently Discard", "Master SessionKey (MSK)", and "Extended Master Session Key (EMSK)" in this document are to be interpreted as described in [RFC3748].This document frequently uses the following terms and abbreviations. The AKA parameters are specified in detail in [TS33.102] for UMTS and [S.S0055-A] for CDMA2000.Arkko & Haverinen Informational [Page 5]AAA protocolAuthentication, Authorization and Accounting protocolAKAAuthentication and Key AgreementAuCAuthentication Centre. The mobile network element that canauthenticate subscribers in the mobile networks.AUTNAKA parameter. AUTN is an authentication value generated bythe AuC, which, together with the RAND, authenticates theserver to the peer, 128 bits.AUTSAKA parameter. A value generated by the peer uponexperiencing a synchronization failure, 112 bits.EAPExtensible Authentication Protocol [RFC3748]Fast Re-AuthenticationAn EAP-AKA authentication exchange that is based on keysderived upon a preceding full authentication exchange. The3rd Generation AKA is not used in the fast re-authenticationprocedure.Fast Re-Authentication IdentityA fast re-authentication identity of the peer, including anNAI realm portion in environments where a realm is used.Used on re-authentication only.Fast Re-Authentication UsernameThe username portion of fast re-authentication identity,i.e., not including any realm portions.Arkko & Haverinen Informational [Page 6]Full AuthenticationAn EAP-AKA authentication exchange that is based on the3rd Generation AKA procedure.GSMGlobal System for Mobile communications.NAINetwork Access Identifier [RFC4282]Identity ModuleIdentity module is used in this document to refer to thepart of the mobile device that contains authentication andkey agreement primitives. The identity module may be anintegral part of the mobile device or it may be an application on a smart card distributed by a mobile operator. USIM and(R)UIM are identity modules.NonceA value that is used at most once or that is never repeatedwithin the same cryptographic context. In general, a nonce can be predictable (e.g., a counter) or unpredictable (e.g., arandom value). Because some cryptographic properties maydepend on the randomness of the nonce, attention should be paid to whether a nonce is required to be random or not. In thisdocument, the term nonce is only used to denote random nonces, and it is not used to denote counters.Permanent IdentityThe permanent identity of the peer, including an NAI realmportion in environments where a realm is used. The permanentidentity is usually based on the IMSI. Used on fullauthentication only.Permanent UsernameThe username portion of permanent identity, i.e., not including any realm portions.Arkko & Haverinen Informational [Page 7]Pseudonym IdentityA pseudonym identity of the peer, including an NAI realmportion in environments where a realm is used. Used on fullauthentication only.Pseudonym UsernameThe username portion of pseudonym identity, i.e., not including any realm portions.RANDAn AKA parameter. Random number generated by the AuC,128 bits.RESAuthentication result from the peer, which, together withthe RAND, authenticates the peer to the server,128 bits.(R)UIMCDMA2000 (Removable) User Identity Module. (R)UIM is anapplication that is resident on devices such as smart cards,which may be fixed in the terminal or distributed by CDMA2000operators (when removable).SQNAn AKA parameter. Sequence number used in the authenticationprocess, 48 bits.SIMSubscriber Identity Module. The SIM is traditionally a smartcard distributed by a GSM operator.SRESThe authentication result parameter in GSM, corresponds tothe RES parameter in 3G AKA, 32 bits.Arkko & Haverinen Informational [Page 8]UAKUIM Authentication Key, used in CDMA2000 AKA. Both theidentity module and the network can optionally generate the UAK during the AKA computation in CDMA2000. UAK is not used inthis version of EAP-AKA.UIMPlease see (R)UIM.USIMUMTS Subscriber Identity Module. USIM is an application thatis resident on devices such as smart cards distributed by UMTS operators.3. Protocol OverviewFigure 1 shows the basic, successful full authentication exchange in EAP-AKA, when optional result indications are not used. Theauthenticator typically communicates with an EAP server that islocated on a backend authentication server using an AAA protocol.The authenticator shown in the figure is often simply relaying EAPmessages to and from the EAP server, but these backend AAAcommunications are not shown. At the minimum, EAP-AKA uses tworoundtrips to authenticate and authorize the peer and generatesession keys. As in other EAP schemes, an identity request/response message pair is usually exchanged first. On full authentication, the peer’s identity response includes either the user’s InternationalMobile Subscriber Identity (IMSI), or a temporary identity(pseudonym) if identity privacy is in effect, as specified inSection 4.1. (As specified in [RFC3748], the initial identityrequest is not required, and MAY be bypassed in cases where thenetwork can presume the identity, such as when using leased lines,dedicated dial-ups, etc. Please see Section 4.1.2 for specification of how to obtain the identity via EAP AKA messages.)After obtaining the subscriber identity, the EAP server obtains anauthentication vector (RAND, AUTN, RES, CK, IK) for use inauthenticating the subscriber. From the vector, the EAP serverderives the keying material, as specified in Section 6.4. The vector may be obtained by contacting an Authentication Centre (AuC) on themobile network; for example, per UMTS specifications, several vectors may be obtained at a time. Vectors may be stored in the EAP serverfor use at a later time, but they may not be reused.Arkko & Haverinen Informational [Page 9]In CDMA2000, the vector may include a sixth value called the UserIdentity Module Authentication Key (UAK). This key is not used inEAP-AKA.Next, the EAP server starts the actual AKA protocol by sending anEAP-Request/AKA-Challenge message. EAP-AKA packets encapsulateparameters in attributes, encoded in a Type, Length, Value format.The packet format and the use of attributes are specified inSection 8. The EAP-Request/AKA-Challenge message contains a RANDrandom number (AT_RAND), a network authentication token (AT_AUTN),and a message authentication code (AT_MAC). The EAP-Request/AKA-Challenge message MAY optionally contain encrypted data, which is used for identity privacy and fast re-authentication support, asdescribed in Section 4.1. The AT_MAC attribute contains a messageauthentication code covering the EAP packet. The encrypted data isnot shown in the figures of this section.The peer runs the AKA algorithm (typically using an identity module) and verifies the AUTN. If this is successful, the peer is talking to a legitimate EAP server and proceeds to send the EAP-Response/AKA-Challenge. This message contains a result parameter that allows the EAP server, in turn, to authenticate the peer, and the AT_MACattribute to integrity protect the EAP message.The EAP server verifies that the RES and the MAC in the EAP-Response/ AKA-Challenge packet are correct. Because protected successindications are not used in this example, the EAP server sends theEAP-Success packet, indicating that the authentication wassuccessful. (Protected success indications are discussed inSection 6.2.) The EAP server may also include derived keyingmaterial in the message it sends to the authenticator. The peer has derived the same keying material, so the authenticator does notforward the keying material to the peer along with EAP-Success.Arkko & Haverinen Informational [Page 10]Peer Authenticator| EAP-Request/Identity ||<------------------------------------------------------|| || EAP-Response/Identity || (Includes user’s NAI) ||------------------------------------------------------>|| +------------------------------+ | | Server runs AKA algorithms, | | | generates RAND and AUTN. | | +------------------------------+ | EAP-Request/AKA-Challenge || (AT_RAND, AT_AUTN, AT_MAC) ||<------------------------------------------------------|+-------------------------------------+ || Peer runs AKA algorithms, | || verifies AUTN and MAC, derives RES | || and session key | |+-------------------------------------+ || EAP-Response/AKA-Challenge || (AT_RES, AT_MAC) ||------------------------------------------------------>|| +--------------------------------+ | | Server checks the given RES, | | | and MAC and finds them correct.| | +--------------------------------+ | EAP-Success ||<------------------------------------------------------|Figure 1: EAP-AKA full authentication procedureArkko & Haverinen Informational [Page 11]Figure 2 shows how the EAP server rejects the Peer due to a failedauthentication.Peer Authenticator| EAP-Request/Identity ||<------------------------------------------------------|| || EAP-Response/Identity || (Includes user’s NAI) ||------------------------------------------------------>|| +------------------------------+ | | Server runs AKA algorithms, | | | generates RAND and AUTN. | | +------------------------------+ | EAP-Request/AKA-Challenge || (AT_RAND, AT_AUTN, AT_MAC) ||<------------------------------------------------------|+-------------------------------------+ || Peer runs AKA algorithms, | || possibly verifies AUTN, and sends an| || invalid response | |+-------------------------------------+ || EAP-Response/AKA-Challenge || (AT_RES, AT_MAC) ||------------------------------------------------------>|| +------------------------------------------+| | Server checks the given RES and the MAC, || | and finds one of them incorrect. || +------------------------------------------+| EAP-Request/AKA-Notification ||<------------------------------------------------------|| EAP-Response/AKA-Notification ||------------------------------------------------------>|| EAP-Failure ||<------------------------------------------------------|Figure 2: Peer authentication failsArkko & Haverinen Informational [Page 12]Figure 3 shows the peer rejecting the AUTN of the EAP server.The peer sends an explicit error message (EAP-Response/AKA-Authentication-Reject) to the EAP server, as usual in AKA whenAUTN is incorrect. This allows the EAP server to produce the sameerror statistics that AKA generally produces in UMTS or CDMA2000.Peer Authenticator| EAP-Request/Identity ||<------------------------------------------------------|| EAP-Response/Identity || (Includes user’s NAI) ||------------------------------------------------------>|| +------------------------------+ | | Server runs AKA algorithms, | | | generates RAND and a bad AUTN| | +------------------------------+ | EAP-Request/AKA-Challenge || (AT_RAND, AT_AUTN, AT_MAC) ||<------------------------------------------------------|+-------------------------------------+ || Peer runs AKA algorithms | || and discovers AUTN that can not be | || verified | |+-------------------------------------+ || EAP-Response/AKA-Authentication-Reject ||------------------------------------------------------>|| EAP-Failure ||<------------------------------------------------------|Figure 3: Network authentication failsThe AKA uses shared secrets between the Peer and the Peer’s homeoperator, together with a sequence number, to actually perform anauthentication. In certain circumstances, shown in Figure 4, it ispossible for the sequence numbers to get out of sequence.Arkko & Haverinen Informational [Page 13]Peer Authenticator| EAP-Request/Identity ||<------------------------------------------------------|| EAP-Response/Identity || (Includes user’s NAI) ||------------------------------------------------------>|| +------------------------------+ | | Server runs AKA algorithms, | | | generates RAND and AUTN. | | +------------------------------+ | EAP-Request/AKA-Challenge || (AT_RAND, AT_AUTN, AT_MAC) ||<------------------------------------------------------|+-------------------------------------+ || Peer runs AKA algorithms | || and discovers AUTN that contains an | || inappropriate sequence number | |+-------------------------------------+ || EAP-Response/AKA-Synchronization-Failure || (AT_AUTS) ||------------------------------------------------------>|| +---------------------------+| | Perform resynchronization || | Using AUTS and || | the sent RAND || +---------------------------+| |Figure 4: Sequence number synchronizationAfter the resynchronization process has taken place in the server and AAA side, the process continues by the server side sending a newEAP-Request/AKA-Challenge message.In addition to the full authentication scenarios described above,EAP-AKA includes a fast re-authentication procedure, which isspecified in Section 5. Fast re-authentication is based on keysderived on full authentication. If the peer has maintained stateinformation for re-authentication and wants to use fastre-authentication, then the peer indicates this by using a specificfast re-authentication identity instead of the permanent identity or a pseudonym identity.Arkko & Haverinen Informational [Page 14]4. Operation4.1. Identity Management4.1.1. Format, Generation, and Usage of Peer Identities4.1.1.1. GeneralIn the beginning of EAP authentication, the Authenticator or the EAP server usually issues the EAP-Request/Identity packet to the peer.The peer responds with EAP-Response/Identity, which contains theuser’s identity. The formats of these packets are specified in[RFC3748].Subscribers of mobile networks are identified with the International Mobile Subscriber Identity (IMSI) [TS23.003]. The IMSI is a stringof not more than 15 digits. It is composed of a Mobile Country Code (MCC) of 3 digits, a Mobile Network Code (MNC) of 2 or 3 digits, and a Mobile Subscriber Identification Number (MSIN) of not more than 10 digits. MCC and MNC uniquely identify the GSM operator and helpidentify the AuC from which the authentication vectors need to beretrieved for this subscriber.Internet AAA protocols identify users with the Network AccessIdentifier (NAI) [RFC4282]. When used in a roaming environment, the NAI is composed of a username and a realm, separated with "@"(username@realm). The username portion identifies the subscriberwithin the realm.This section specifies the peer identity format used in EAP-AKA. In this document, the term identity or peer identity refers to the whole identity string that is used to identify the peer. The peer identity may include a realm portion. "Username" refers to the portion of the peer identity that identifies the user, i.e., the username does notinclude the realm portion.4.1.1.2. Identity Privacy SupportEAP-AKA includes optional identity privacy (anonymity) support thatcan be used to hide the cleartext permanent identity and thereby make the subscriber’s EAP exchanges untraceable to eavesdroppers. Because the permanent identity never changes, revealing it would helpobservers to track the user. The permanent identity is usually based on the IMSI, which may further help the tracking, because the sameidentifier may be used in other contexts as well. Identity privacyis based on temporary identities, or pseudonyms, which are equivalent Arkko & Haverinen Informational [Page 15]to but separate from the Temporary Mobile Subscriber Identities(TMSI) that are used on cellular networks. Please see Section 12.1for security considerations regarding identity privacy.4.1.1.3. Username Types in EAP-AKA IdentitiesThere are three types of usernames in EAP-AKA peer identities:(1) Permanent usernames. For example,0123456789098765@ might be a valid permanent identity. In this example, 0123456789098765 is the permanent username.(2) Pseudonym usernames. For example, 2s7ah6n9q@ might be a valid pseudonym identity. In this example, 2s7ah6n9q is thepseudonym username.(3) Fast re-authentication usernames. For example,43953754@ might be a valid fast re-authenticationidentity. In this case, 43953754 is the fast re-authenticationusername. Unlike permanent usernames and pseudonym usernames, fastre-authentication usernames are one-time identifiers, which are notre-used across EAP exchanges.The first two types of identities are used only on fullauthentication, and the last type only on fast re-authentication.When the optional identity privacy support is not used, thenon-pseudonym permanent identity is used on full authentication. The fast re-authentication exchange is specified in Section 5.4.1.1.4. Username DecorationIn some environments, the peer may need to decorate the identity byprepending or appending the username with a string, in order toindicate supplementary AAA routing information in addition to the NAI realm. (The usage of an NAI realm portion is not considered to bedecoration.) Username decoration is out of the scope of thisdocument. However, it should be noted that username decoration might prevent the server from recognizing a valid username. Hence,although the peer MAY use username decoration in the identities that the peer includes in EAP-Response/Identity, and although the EAPserver MAY accept a decorated peer username in this message, the peer or the EAP server MUST NOT decorate any other peer identities thatare used in various EAP-AKA attributes. Only the identity used inEAP-Response/Identity may be decorated.Arkko & Haverinen Informational [Page 16]。