0

我需要一种算法来生成一种 OTP 代码。

  • 6位输出（小数补'0'）

  • 没有状态数据（或 DB）

  • 每个号码将至少以 1ms 的间隔（通常为几秒）被选中

  • 一个小时后号码可以重复使用

我的第一次尝试：

  • 用当前时间做一个种子号。
    17:12:12.033 => (12 * 60 + 12) * 1000 + 33 = 73233 enter code here （小时值被删除。所以这有 1 小时的周期）

  • 最多6位数，计算999999的提醒。
    （73233 mod 999999）+ 1= 73234 => 073234

  • 但是，为了不显示顺序增加，在mod
    ((73233 * 123456) mod 999999) + 1 = 62290 => 062290 之前乘以一个随机数

  • 为避免在零秒时输出 0，请在mod
    ((73233 * 123456 + 123456) mod 999999) + 1 = 185746 之前添加一个随机数

17:00:00.000 => 123457
17:00:00.001 => 246914
17:00:01.000 => 469069
17:01:00.000 => 860197
...
17:59:59.999 => 314956 Wolfram Alpha

它是否足够独特？

我如何声称或证明该方案在数学上有效？

纠正了错误。

4

4 回答 4

1

许多 PRNG 算法实际上具有内置的唯一性。检查其中一些http://en.wikipedia.org/wiki/List_of_random_number_generators

于 2014-06-03T11:38:55.263 回答
1

你所做的几乎所有事情都是错误的。

  • 在时间之外创建种子需要毫秒前的 1000 倍：(12*60+12)*1000+33=732033

  • 要制作 6 位数字，您需要用 1000000 创建余数。

  • 在隐藏序列算法时，与（常数）数相乘几乎总比没有好。

  • 最后，虽然添加一个常数可以避免结果为 0，但它也可能导致结果为 0，机会均等。

您最好从某种要求开始，例如：

  • 结果不能为 0。
  • 顺序必须很难甚至不可能猜到。
  • ... 也许更多。

然后，也只有这样，你才能开始设计算法。这是它可能看起来的粗略轮廓。

如果基于时间的结果对您来说足够好，那就去吧。但是没有理由停在分钟，你也可以包括小时和日，月和年，比如

seed=2014-06-02T17:03:12.033

然后在它上面附加某种秘密盐，所以结果看起来像

seed=2014-06-02T17:03:12.033.$d#xg9s2]/

然后应用哈希函数。如果您需要最高安全性，请选择安全哈希，例如 SHA1。如果您喜欢更好的性能，请选择一个简单的，例如Murmurhash。这里的结果是一个随机数H。然后，并且只有在那时，应用该mod功能，将结果带入您想要的范围。如果结果可能在 [0..999999] 内，则必须计算H mod 1000000. 如果结果范围应该是 [1..999999] 你计算H mod 999999 + 1. 其他范围也类似。

于 2014-06-03T11:41:46.430 回答
0

感谢@jva。

OP 的（我的）方法本质上是一个多项式全等生成器，但很糟糕。
=>线性同余生成器

LCG 由递归关系定义：

X{n+1} = ( a X{n} + c ) mod m

链接的维基百科文章有几个众所周知的参数。

但是 OP 的方法并没有保留之前的输出。只不过是每次都播种随机数生成器。这完全脱离了上下文。证明它的质量远远超出了通常的编程 QA 的范围。

我建议另一种方法：

1) 用当前时间组成一个 int 值
2) 使用 32 位分组密码对其进行加密
3) 使用加密输出生成 6 位数字

对于密码，请注意此 SO post Way to encrypt a single int和此 GitHub 项目Skip32-java (for Java)。C 源代码也可在另一个 GitHub 项目crypt-skip32-xs中找到。

public class Test {
    public static void main(String[] args) throws Exception {
        byte[] zeros = new byte[10];
        for (int i=0; i<1000; ++i) {
            Thread.sleep(1);
            int v1 = (int)System.currentTimeMillis();
            int v2 = Skip32.encrypt(v1, zeros);
            int v3 = v2;
            if (v3 < 0)
                v3 += Integer.MAX_VALUE;
            v3 = v3 % 999999 + 1;
            String s2 = String.format("%12d", v2);
            String s3 = String.format("%06d", v3);
            System.out.println(v1 + "\t" + s2 + "\t" + s3);
        }
    }
}

样本输出：

1655158217    1226572185    573412
1655158239     -42142206    343547
1655158240    -125054465    431205
1655158241   -1945330164    153686
1655158242    1278935533    936812
1655158243    1551082446    083998
1655158244    2092977447    979540
1655158245     508798123    798632
1655158246    1015384462    385478
1655158247    1924275560    277485
1655158248   -1285791225    693284
1655158249    -230064345    421220
1655158250     492942608    943101
1655158251   -1583835512    648699
1655158252   -2032608363    875399
1655158253     633954047    954681
1655158254    -274091626    393895
1655158255   -1904398830    085061
1655158256     280153665    153946
1655158257    -444360271    125080
1655158258    1092738103    739196
1655158259   -1320398852    085623
1655158260     353033065    033419
1655158261    1497312415    313913
1655158262     502821330    821833
  • 由于将 32 位四舍五入为 6 位，可能会发生冲突。
  • 此代码的目的是展示一种从时间值生成随机映射的方法。
于 2014-06-03T15:31:23.090 回答
0

我发现（通过测试）在没有状态保存的情况下，所有提到的方法都容易受到非常短周期的碰撞。在不多的测试运行中，相同的数字在 30 秒内被选中。

我认为使用mod不保留状态的操作不能产生随机均匀分布（没有密码分析级别的发明）。

所以我试图找到简单的数字改组方案。
我将重用时间缩短到 10 分钟。
经过一番测试，我随机选择了以下公式： 

V = (Minute % 10) * 1235 + Second * 79 + Millisecond * 982 + 1

这个公式正好生成 10 分钟。周期随机数序列。
（我没查，但看起来分布均匀）

对于我目前的需求，这种方法可以完成工作。

示例 Java 代码： 

public void run() {
    try {
        while (true) {
            Thread.sleep(1);

            Date now = new Date();
            Calendar cal = Calendar.getInstance();
            cal.setTime(now);
            int m = cal.get(Calendar.MINUTE);
            int s = cal.get(Calendar.SECOND);
            int ms = cal.get(Calendar.MILLISECOND);
            String ts = String.format("%02d:%02d:%03d", m, s, ms);

            int v = (m % 10) * 1235 + s * 79 + ms * 982 + 1;
            String ret = String.format("%06d", v);

            System.out.println(ts + "\t" + ret);
        }
    }
    catch (Exception e) {
        System.out.println(e);
    }
}

样本输出： 

MM:SS:M.S   V  

09:40:806   805768
09:40:807   806750
09:40:808   807732
09:40:809   808714
09:40:810   809696
09:40:811   810678
09:40:812   811660
09:40:813   812642
09:40:814   813624
09:40:815   814606
09:40:816   815588
09:40:817   816570
09:40:818   817552
09:40:819   818534
09:40:820   819516
09:40:821   820498
09:40:822   821480
09:40:823   822462
09:40:824   823444
09:40:825   824426
09:40:826   825408
09:40:827   826390
09:40:828   827372
09:40:829   828354
09:40:830   829336
09:40:831   830318
09:40:832   831300
09:40:833   832282
09:40:834   833264
09:40:835   834246
09:40:836   835228
09:40:837   836210
09:40:838   837192
09:40:839   838174
09:40:840   839156
09:40:841   840138
09:40:842   841120
09:40:843   842102
09:40:844   843084
09:40:845   844066
09:40:846   845048
09:40:847   846030
09:40:848   847012
09:40:849   847994
09:40:850   848976
09:40:851   849958
09:40:852   850940
09:40:853   851922
09:40:854   852904
09:40:855   853886
09:40:856   854868
09:40:857   855850
09:40:858   856832
09:40:859   857814
09:40:860   858796
09:40:861   859778
09:40:862   860760
09:40:863   861742
09:40:864   862724
09:40:865   863706
09:40:866   864688
09:40:867   865670
09:40:868   866652
09:40:869   867634
09:40:870   868616
09:40:871   869598
09:40:872   870580
09:40:873   871562
09:40:874   872544
09:40:875   873526
09:40:876   874508
09:40:877   875490
09:40:878   876472
09:40:879   877454
09:40:880   878436
09:40:881   879418
09:40:882   880400
09:40:883   881382
09:40:884   882364
09:40:885   883346
09:40:886   884328
09:40:887   885310
09:40:888   886292
09:40:889   887274
09:40:890   888256
09:40:891   889238
09:40:892   890220
09:40:893   891202
09:40:894   892184
09:40:895   893166
09:40:896   894148
09:40:897   895130
09:40:898   896112
09:40:899   897094
09:40:900   898076
09:40:901   899058
09:40:902   900040
09:40:903   901022
09:40:904   902004
09:40:905   902986
09:40:906   903968
09:40:907   904950
09:40:908   905932
09:40:909   906914
09:40:910   907896
09:40:911   908878
09:40:912   909860
09:40:913   910842
09:40:914   911824
09:40:915   912806
09:40:916   913788
09:40:917   914770
09:40:918   915752
09:40:919   916734
09:40:920   917716
09:40:921   918698
09:40:922   919680
09:40:923   920662
09:40:924   921644
09:40:925   922626
09:40:926   923608
09:40:927   924590
09:40:928   925572
09:40:929   926554
09:40:930   927536
09:40:931   928518
09:40:932   929500
09:40:933   930482
09:40:934   931464
09:40:935   932446
09:40:936   933428
09:40:937   934410
09:40:938   935392
09:40:939   936374
09:40:940   937356
09:40:941   938338
09:40:942   939320
09:40:943   940302
09:40:944   941284
09:40:945   942266
09:40:946   943248
09:40:947   944230
09:40:948   945212
09:40:949   946194
09:40:950   947176
09:40:951   948158
09:40:952   949140
09:40:953   950122
09:40:954   951104
09:40:955   952086
09:40:956   953068
09:40:957   954050
09:40:958   955032
09:40:959   956014
09:40:960   956996
09:40:961   957978
09:40:962   958960
09:40:963   959942
09:40:964   960924
09:40:965   961906
09:40:966   962888
09:40:967   963870
09:40:968   964852
09:40:969   965834
09:40:970   966816
09:40:971   967798
09:40:972   968780
09:40:973   969762
09:40:974   970744
09:40:975   971726
09:40:976   972708
09:40:977   973690
09:40:978   974672
09:40:979   975654
09:40:980   976636
09:40:981   977618
09:40:982   978600
09:40:983   979582
09:40:984   980564
09:40:985   981546
09:40:986   982528
09:40:987   983510
09:40:988   984492
09:40:989   985474
09:40:990   986456
09:40:991   987438
09:40:992   988420
09:40:993   989402
09:40:994   990384
09:40:995   991366
09:40:996   992348
09:40:997   993330
09:40:998   994312
09:40:999   995294
09:41:000   014355
09:41:001   015337
09:41:002   016319
09:41:003   017301
09:41:004   018283
09:41:005   019265
09:41:006   020247
09:41:007   021229
09:41:008   022211
09:41:009   023193
09:41:010   024175
09:41:011   025157
09:41:012   026139
09:41:013   027121
09:41:014   028103
09:41:015   029085
09:41:016   030067
09:41:017   031049
09:41:018   032031
09:41:019   033013
09:41:020   033995
09:41:021   034977
09:41:022   035959
09:41:023   036941
09:41:024   037923
09:41:025   038905
09:41:026   039887
09:41:027   040869
09:41:028   041851
09:41:029   042833
09:41:030   043815
09:41:031   044797
09:41:032   045779
09:41:033   046761
09:41:034   047743
09:41:035   048725
09:41:036   049707
09:41:037   050689
09:41:038   051671
09:41:039   052653
09:41:040   053635
09:41:041   054617
09:41:042   055599
09:41:043   056581
09:41:044   057563
09:41:045   058545
09:41:046   059527
09:41:047   060509
09:41:048   061491
09:41:049   062473
09:41:050   063455
09:41:051   064437
09:41:052   065419
09:41:053   066401
09:41:054   067383
09:41:055   068365
09:41:056   069347
09:41:057   070329
09:41:058   071311
09:41:059   072293
09:41:060   073275
09:41:061   074257
09:41:062   075239
09:41:063   076221
09:41:064   077203
09:41:065   078185
09:41:066   079167
09:41:067   080149
09:41:068   081131
09:41:069   082113
09:41:070   083095
09:41:071   084077
09:41:072   085059
09:41:073   086041
09:41:074   087023
09:41:075   088005
09:41:076   088987
09:41:077   089969
09:41:078   090951
09:41:079   091933
09:41:080   092915
09:41:081   093897
09:41:082   094879
09:41:083   095861
09:41:084   096843
09:41:085   097825
09:41:086   098807
09:41:087   099789
09:41:088   100771
09:41:089   101753
09:41:090   102735
09:41:091   103717
09:41:092   104699
09:41:093   105681
09:41:094   106663
09:41:095   107645
09:41:096   108627
09:41:097   109609
09:41:098   110591
09:41:099   111573
09:41:100   112555
09:41:101   113537
09:41:102   114519
09:41:103   115501
09:41:104   116483
09:41:105   117465
09:41:106   118447
09:41:107   119429
09:41:108   120411
09:41:109   121393
09:41:110   122375
09:41:111   123357
09:41:112   124339
09:41:113   125321
09:41:114   126303
09:41:115   127285
09:41:116   128267
09:41:117   129249
09:41:118   130231
09:41:119   131213
09:41:120   132195
09:41:121   133177
09:41:122   134159
09:41:123   135141
09:41:124   136123
09:41:125   137105
09:41:126   138087
09:41:127   139069
09:41:128   140051
09:41:129   141033
09:41:130   142015
09:41:131   142997
09:41:132   143979
09:41:133   144961
09:41:134   145943
09:41:135   146925
09:41:136   147907
09:41:137   148889
09:41:138   149871
09:41:139   150853
09:41:140   151835
09:41:141   152817
09:41:142   153799
09:41:143   154781
09:41:144   155763
09:41:145   156745
09:41:146   157727
09:41:147   158709
09:41:148   159691
09:41:149   160673
09:41:150   161655
09:41:151   162637
09:41:152   163619
09:41:153   164601
09:41:154   165583
09:41:155   166565
09:41:156   167547
09:41:157   168529
09:41:158   169511
09:41:159   170493
09:41:160   171475
09:41:161   172457
09:41:162   173439
09:41:163   174421
09:41:164   175403
09:41:165   176385
09:41:166   177367
09:41:167   178349
09:41:168   179331
09:41:169   180313
09:41:170   181295
09:41:171   182277
09:41:172   183259
09:41:173   184241
09:41:174   185223
09:41:175   186205
于 2014-06-05T05:21:55.723 回答