0

I need an algorithm for generating a kind of OTP codes.

  • 6 digit output (pad '0' for small number)

  • No state data (or DB)

  • Each number will be picked at least 1ms interval (usually a few seconds)

  • Numbers can be reused after an hour

My first attempt:

  • Make a seed number with the current time.
    17:12:12.033 => (12 * 60 + 12) * 1000 + 33 = 73233 enter code here (hour value is dropped. So this has 1 hour period)

  • To make at most 6 digits, calculate reminder of 999999.
    (73233 mod 999999) + 1= 73234 => 073234

  • But, not to reveal sequential increasing, multiply with a random number before mod
    ((73233 * 123456) mod 999999) + 1 = 62290 => 062290

  • To avoid 0 output at zero second, add a random number before 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


Could it be sufficiently unique?

How can I claim or prove this scheme will work mathematically?


Corrected mistakes.

8
  • sufficiently unique for what? You will also want to make sure that the modulus and the multiplier do not have a common factor (other than 1). To see why, note that all your generated numbers are divisible by 3.
    – Henry
    Jun 3, 2014 at 11:16
  • In the line 17:12:12.033 => (12 * 60 + 12) * 100 + 33 = 73233 you multiply the number of seconds by 100 and then add the milliseconds. Did you mean to multiply by 1000?
    – Salix alba
    Jun 3, 2014 at 11:16
  • 1
    Do you need to prove correctness of your algorithm or find something better? From my point of view, second option is more perspective.
    – Ilya
    Jun 3, 2014 at 11:17
  • 6 digits encode a maximum of one million numbers. At worse, you'll need 60 x 60 x 1000 = 3,600,000 numbers per hour. It doesn't fit ! Okay for 1,000 numbers per hour, but the probability of a random collision is at least 0.001.
    – user1196549
    Jun 3, 2014 at 12:44
  • "Each number will be picked at least 1ms interval" - is this guaranteed, or have you made this rule up? Jun 3, 2014 at 15:35

4 Answers 4

1

Many PRNG algorithms actually have uniqueness built in. Check some of these http://en.wikipedia.org/wiki/List_of_random_number_generators

1
  • but how do I ensure uniquenese without preserving the seed?
    – 9dan
    Jun 3, 2014 at 12:39
1

Almost everything you have done is wrong.

  • Creating a seed out of the time requires a factor of 1000 before the milliseconds: (12*60+12)*1000+33=732033

  • To make 6 digits you need to create the remainder with 1000000.

  • Multiplication with a (constant) number is hardly better than nothing when it comes to hiding the sequence algorithm.

  • Finally, while adding a constant may avoid a result of 0, it might as well cause a result of 0, with equal chance.

You better start with some sort of requirements, like e.g.:

  • The result must not be 0.
  • The sequence must be hard to impossible to guess.
  • ... maybe more.

Then, and only then, you can start designing an algorithm. Here is a rough outline what it might look like.

If a time-based result is good enough for you, then go with it. But then there is no reason to stop at the minutes, you can as well include hour and day and month and year, like

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

Then attach some sort of secret salt to it, so the result looks like

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

Then apply a hash function. If you need top-security pick a secure hash, like SHA1. If you prefer better performance pick a simple one, like Murmurhash. The result here is a random number H. Then, and only then, apply the mod function, to bring the result into your desired range. If the result may be within [0..999999], you have to calulate H mod 1000000. If the result range should be [1..999999] you calculate H mod 999999 + 1. Similarly for other ranges.

6
  • Thanks for corrections. But multipling with a constant is the method of Linear congruential generator. Not that bad, I think.
    – 9dan
    Jun 3, 2014 at 13:00
  • @9dan There it's being used to create predictable random numbers. But you want unpredictable random numbers. Jun 3, 2014 at 13:05
  • When H mod 1000000 is calculated, where H is fairly random one would expect a number to repeat after only about 1000 numbers due to the birthday paradox.
    – Henry
    Jun 3, 2014 at 14:22
  • Right. So what. This isn't a problem for a one-time password, the probability of guessing a password is still 1/1000000 Jun 3, 2014 at 16:33
  • @pentadecagon agreed, but OP has asked for numbers that are unique in one hour. This cannot be guranteed by using a hash.
    – Henry
    Jun 3, 2014 at 17:31
0

Thanks to @jva.

OP's (my) method is essentially a polynomial congruent generator, but bad one.
=> Linear congruential generator

LCG is defined by the recurrence relation:

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

Linked Wikipedia article has several well known parameters.

But OP's method doesn't keep the previous output. It is nothing but seeding the random number generator every time. It is totally out of the context. To prove it's quality is well beyond the scope of usual programming QA.

I suggest another method:

1) make up a int value with the current time
2) encrypt it with a 32 bit block cipher
3) generate 6 digits with the encrypted output

For cipher, note this SO post Way to encrypt a single int and this GitHub project Skip32-java (for Java). C source also available in another GitHub project 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);
        }
    }
}

Sample output:

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
  • There are possibilities of collision due to rounding 32 bits into 6 digits.
  • Purpose of this code is to show a method of generating random mapping from the time value.
0

I found that (by testing) without state preserving, all of the mentioned methods are susceptible to very short period collisions. In not many test running, the same numbers are picked under 30 seconds.

I think using mod operations without preserving the state is can not produce random uniform distribution (without crypto analysis level invention).

So I tried to find simple number shuffling scheme.
I reduced the reusing period to 10 minutes.
After some test, I randomly picked below formula:

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

This formula generate exactly 10 min. period random number sequence.
(I didn't checked, but it looks uniformly distributed)

For my current needs, this method will do the work.

Sample Java code:

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);
    }
}

Sample output:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.