Board logo

標題: 有無較短, 而踫撞機率又相對較低既random key? [打印本頁]
作者: 3ldk    時間: 2016-7-7 16:47     標題: 有無較短, 而踫撞機率又相對較低既random key?

https://www.google.com.hk/search ... oq=uuid+alternative

https://www.google.com.hk/search ... oq=uuid+lightweight

搵左少少資料, 但無結果

128bit UUID的確係踫撞率好低, 但實在太低, 過晒頭

我希望條key可以短D, 足夠用就得, 10個char對我黎講已經好夠用, 甚至再短D, 32bit(8char)都夠晒

目前有咩algorithm既result短得黎, 離散度又夠高?
作者: ykmran    時間: 2016-7-7 17:07

點解唔就咁random gen 8個[0-9A-Za-z_]char出黎？
作者: 3ldk    時間: 2016-7-7 17:13

點解唔就咁random gen 8個[0-9A-Za-z_]char出黎？
ykmran 發表於 2016-7-7 17:07



咁點樣可以係唔消耗大量space既情況下, make sure gen出黎既key踫撞率盡量低?
作者: bugtester    時間: 2016-7-7 17:31

what is your purpose? use sha, md5 to hash a sequence number already able to generate a low collision key.
作者: 燕飛    時間: 2016-7-7 17:33

要Random 定 要Key?

via HKEPC Reader for Android
作者: 3ldk    時間: 2016-7-7 18:05

想要一個random string

關於話一般hash夠晒低
其實我簡單做過下依方面的research
其中一個result
https://www.zhihu.com/question/23940415

雖然唔知佢係咩hash, 但根據依個結果, 估計一般唔會理想

當然, 我會再搵多D資料, 睇下有無測試常見的32bit hash的離散程度如何
作者: masseffect    時間: 2016-7-7 18:08

點解要random?，唔要random 嘅話用seq更好

如果真係要random
俾你用到32bit, 一條record慳左96bit，即係12個char...
要自己搞一餐，仲唔知會唔會有bug，你覺得抵唔抵？

另外，32 bit肯定唔夠，你睇返wiki birthday problem個table
如果你有5萬條records，有25%機會會有一個以上嘅Key 撞左...
而你慳左唔夠1MB
作者: 3ldk    時間: 2016-7-7 18:41

條key唔係用黎做id, 係比user用, 雖然唔係用黎比user記, 但正常一個人見到堆無意思既string, 10個位已經係極限, 再多會另人反感, 影響使用率

而我亦無預條key唔會撞, 本身其實就係預左重用都盡量唔會有問題
只係希望撞與撞之間既時間可以盡量耐D



而我所講既"唔消耗大量space", 唔係指儲data用既space, 而係gen key用既space
講真我可以由000...000 至 zzz...zzz, 將所有組合gen晒出黎, 然後撈亂佢地, 再逐個派, 咁就可以最大程度地保證離散度
但咁就要用space儲起晒依堆key, 又再maintain多一個table, 我想避免
作者: 燕飛    時間: 2016-7-7 18:43

回復 8 #3ldk

直接派咪算  random = 晒 gas

via HKEPC Reader for Android
作者: chenathcx    時間: 2016-7-7 18:54

回復 3ldk

直接派咪算  random = 晒 gas

via HKEPC Reader for Android
燕飛 發表於 2016-7-7 18:43



    http://cmc925.blogspot.hk/2013/07/blog-post_8.html
諗起為何造輪

講返正題, 我諗樓主唔想比人撞到個string, 所以唔順序派
作者: ykmran    時間: 2016-7-7 19:02

我諗最後樓主最後會死死氣自己係/dev/random拎32個byte
作者: 燕飛    時間: 2016-7-7 19:02

本帖最後由 燕飛 於 2016-7-7 19:06 編輯

回復 10 #chenathcx

又唔係要做 hash table
求其 gen random
撞左咪再 gen 過

其實用 LFSR 就solve 到

via HKEPC Reader for Android
作者: winstercafe    時間: 2016-7-7 19:07

條key唔係用黎做id, 係比user用, 雖然唔係用黎比user記, 但正常一個人見到堆無意思既string, 10個位已經係 ...
3ldk 發表於 2016-7-7 18:41

一般確認 SMS 都只係六個位
有效時間控制嚮幾分鐘內
你既然唔係要 KEY
random 10萬個 combination 仲唔夠？
作者: starone    時間: 2016-7-7 19:49

你係咪想做 類似 short url o的Key ???
作者: rabbit82047    時間: 2016-7-7 20:21

講真條 key 要俾 user 用, 本身就應該有 table 裝住
你 random gen 條新 key 再同 existing key 對下就得
實際意義上 space cost = 0
作者: 3ldk    時間: 2016-7-7 21:01

你係咪想做 類似 short url o的Key ???
starone 發表於 2016-7-7 19:49



非常類似, 不過依個application既用法一般網上唔會有機會見到
而一般short url我估計係用派既方法, 因為佢地條key一般都真係好短, 但保持既時間又相當長



-------------------------------

有建議用search之前既key的方法
假如key有10個位, 唔用大階, 唔用符號, 會有咁多位
https://www.google.com.hk/webhp? ... w=1&q=37+%5E+10

一般active既key有7M左右, 如果計埋其他, 實際table records再多幾倍

我無測試過, 但隨便google下, 大約估計到應該係慢的
https://www.google.com.hk/webhp? ... 20in%205m%20records


-----------------------------

溫馨提示一下, 依個其實只係一個問有咩algor的問題


------------------------

派key既方法我其實真係有認真考慮過, 不過因為諗唔到點做, 所以hold住左
正如上面講, 就算唔計大階符號, 都有咁多位
https://www.google.com.hk/webhp? ... w=1&q=37+%5E+10
要點樣係咁多records入面快速抽出最後一個出黎, 又快速mark住用到去邊, 依個未諗到
作者: FlyingForever    時間: 2016-7-7 22:36

樓主要random既目的係咩先？
如果只係唔重複，sequence已經ok

方法一：搵個32 bit既block cipher，gen一條static既key，然後每次encrypt 32 bit sequence number

之所以唔用stream cipher，係因為stream cipher基本上係一個psuedorandom number generator，用條key gen一個random number然後同plaintext XOR
所以如果你知道00000000...000 encrypt完係10111101...101，由XOR性質你已經知道00000000...001 encrypt完一定係10111101...100
更進一步講，因為stream cipher逐byte逐byte食input，所以頭果byte 00000000一定係出返10111101
咁易比人估到既話不如直接用sequence……

方法二：random gen 32 bit，然後落bloom filter

方法一優點：
需要既空間少，只需要儲一條key
由於用空間少而且唔會變，完全可以program一load就連埋條key load入RAM，甚至hardcode入program，所以runtime冇disk IO，會快D
100%唔會撞，因為cipher保證可以解密，意味住input同output一一對應

方法一缺點：
因為block只有32bit，所以只要知道cipher、sequence number同output，就可以硬爆返條key出黎，然後預測未來既output

方法二優點：
無法預測，因為你係每次都random gen

方法二缺點：
有機會撞，因為用左bloom filter
就算犧牲碰撞機率去令佔用空間變細，但你個bloom filter會改，最終都要serialize，避唔開disk IO
作者: YuiNarusawa    時間: 2016-7-8 01:00

redeem code o個d唔需理會security既野一向用Hashids, 只要直接hash個auto increment 既id就得
作者: chi251155    時間: 2016-7-8 02:35

本帖最後由 chi251155 於 2016-7-8 02:37 編輯

假設alphabet有[a-z0-9]共36個char
用trie儲既話complete左每個node有36個subnodes
每個node要(8*36+1)B
如果generate random string of len#要 space and total combinations
#1 10KB - 36
#2 366KB - 1,296
#3 12.9MB - 46,656
#4 463MB - 1,679,616
#5 16.27GB - 60,466,176
#6 586GB - 2,176,682,336
#7 20.6TB 78,364,164,096
#8 742TB - 2,821,109,907,456
collision就backtrace dfs去下一個leaf，如果唔怕比人估到可以順序添咁樣就行n層就出到key

其實你要7M條key 5個位都已經幾夠下 16GB memory都夠放
作者: rabbit82047    時間: 2016-7-8 14:06

唔明點解唔 query db, 撞左再 gen, 簡單方便
因為條 key 實際要用, 最終點都要 query db

7M log base 2 ~ 22.x, btree index 足夠,
以宜家既 hw, 應該係 0.x ms 內既事, 再要快可以用 hash index
7M / 36 ^ 5, clash probability 係 ~11.6%,
7M / 36 ^ 6, ~0.3%,
最多都係 query 兩次左右

===
不過玩下提下個土炮方法, 無實作過:
d = digit, [a-z0-9], 36
l = character len, 5
p = partition, 1024
t = d ^ l
s = sequence number

開個 char array 放 possible chars 再 shuffle
t/p * (s % p) + floor(s/p), 求到新 number, n
將 n 以 base 36 convert 做 int array, 然後 map 返 chars array, 得到一條 key
另外開個 pool, 假設 128, 重複直至填滿 (pool size 決定 randomness)
每次攞 key 就係 pool 度 random 抽一條, 然後 refill

因為實際上都係依 sequence number gen key, 所以唔會有踫撞
加上做左少少 obfuscation, 要破解都要花 D 功夫搵 pattern
而且最後一步係純 random, 搵到 pattern 都係要撞
作者: 3ldk    時間: 2016-7-8 20:19

樓主要random既目的係咩先？
如果只係唔重複，sequence已經ok

方法一：搵個32 bit既block cipher，gen一條 ...
FlyingForever 發表於 2016-7-7 22:36



目的係唔想比人撞到
但又唔介意重複, 不過就希望重複既出現時間可以盡量延長

你個方法一睇落唔錯, 但下面有個更好既方法, 因為唔洗自己implement
作者: 3ldk    時間: 2016-7-8 20:50

redeem code o個d唔需理會security既野一向用Hashids, 只要直接hash個auto increment 既id就得 ...
YuiNarusawa 發表於 2016-7-8 01:00



你依個簡直就係accepted answer
而且佢做到既比我所要求既更多, 本來我唔需要100% unique, 但佢都可以做到
更正既係, 仲可以decode, 咁即係我可以用sequence id save, 用random key 公開
基本上依個係最接近完美既方案

之所以話"最接近", 因為依個方法都有幾個缺點

1. 首先佢無辦法ensure個長度, 佢個網站聲稱無collision, 但我唔信, 因為依個世上有Pigeonhole principle, 所以我測試過, set一個好細既output長度, 再比一個好大既sequence, 最後發現, 原來所謂既無collision, 只不過係當唔夠位, 就不斷加大output長度

2. 同埋佢只係保證salt一樣既情況下係unique, 如果salt改左, 有機會有collision

3. 需要有一個auto increment id, 有時如果個application係唔需要db, 你都需要夾硬整個dummy table, insert dummy record, 全部只係為左想要一個auto increment id


當然, 優點完全可以蓋過以上缺點, 所以依D缺點其實都唔太緊要
作者: 梁炳    時間: 2016-7-8 22:26

本帖最後由 梁炳 於 2016-7-8 22:33 編輯

HashIds，完
http://hashids.org/

只要"random key"唔係指定長度，當然可以在algorithm確保無重覆
Salt係唔suppose會改的，要改就會全部都唔同哂，一樣係唔會重覆架
仲可以用來encode multiple values
作者: FlyingForever    時間: 2016-7-8 23:55

你依個簡直就係accepted answer
而且佢做到既比我所要求既更多, 本來我唔需要100% unique, 但佢都可以做 ...
3ldk 發表於 2016-7-8 20:50

而家先知有樣野叫hashids…
我個方法基本上一樣，不過佢提供左一個任意bit既block cipher，然後按input大細揀用幾多bit

你所講既「缺點」基本上冇可能避開：
1. 你都知道Pigeonhole principle，冇計
2. 無論你用咩algorithm，只要係沿用同一個模式，成個function就只depends on sequence number同salt
其中salt決定permutation of output space，sequence number決定用呢個permutation入面既第幾個output
假設你個space大細係2^32，然後你已經output左2^31個value
呢個時候你轉salt，然後繼續increment sequence number去做output
要係呢種情況下唔撞，只可能係新salt同舊salt既頭2^31個output一樣（次序可以唔同），尾2^31個output都一樣
由於salt可以係任意，意味住對所有salt，頭2^31個output都一樣，尾2^31個output都一樣
將2^31換成arbitrary number，你會發現要符合「轉salt都唔撞」既唯一方法，就係所有salt都用同一set permutation，即係冇salt
3. 成個function只有sequence number係會變既input，冇埋既話只能用random
作者: rabbit82047    時間: 2016-7-11 19:15

本帖最後由 rabbit82047 於 2016-7-11 19:18 編輯

為左重複發明輪子, 所以將自己既諗法實作左
  1. // Example usage:
  2. // HashSequenceGenerator generator = new HashSequenceGenerator("0123456789", 5);
  3. // System.out.println(generator.nextKey());

  5. import java.util.Random;

  7. public class HashSequenceGenerator {
  8.     private long seed, total;

  10.     private char[] availableChars;

  12.     // Character mapper for each character place, this will make the result key looks like random.
  13.     private char[][] chars;

  15.     private int length, seq;

  17.     public HashSequenceGenerator(String availableChars, int length) {
  18.         this(availableChars.toCharArray(), length, new Random().nextLong());
  19.     }

  21.     public HashSequenceGenerator(String availableChars, int length, long seed) {
  22.         this(availableChars.toCharArray(), length, seed);
  23.     }

  25.     public HashSequenceGenerator(char[] availableChars, int length) {
  26.         this(availableChars, length, new Random().nextLong());
  27.     }

  29.     public HashSequenceGenerator(char[] availableChars, int length, long seed) {
  30.         this(availableChars, length, 0, seed);
  31.     }

  33.     public HashSequenceGenerator(char[] availableChars, int length, int seq, long seed) {
  34.         this.seed = seed;
  35.         this.availableChars = availableChars;

  37.         initializeChars(availableChars, length, seed);

  39.         this.total = (long)(Math.pow(availableChars.length, length));
  40.         this.length = length;
  41.         this.seq = seq;
  42.     }

  44.     // Result will be determined by seed
  45.     private void initializeChars(char[] availableChars, int length, long seed) {
  46.         Random random = new Random(seed);

  48.         this.chars = new char[length][availableChars.length];

  50.         for (char[] aChar : chars) {
  51.             System.arraycopy(availableChars, 0, aChar, 0, aChar.length);
  52.             shuffle(aChar, random);
  53.         }
  54.     }

  56.     private int randomInteger(int min, int max, Random randomGenerator) {
  57.         if (min == max) {
  58.             return min;
  59.         }
  60.         return (int)((randomGenerator.nextDouble() * (max - min + 1)) + min);
  61.     }

  63.     private void shuffle(char[] chars, Random random) {
  64.         for (int i = 0; i < chars.length; i++) {
  65.             int idx = randomInteger(0, chars.length-1, random);

  67.             if (i != idx) {
  68.                 char c = chars[i];
  69.                 chars[i] = chars[idx];
  70.                 chars[idx] = c;
  71.             }
  72.         }
  73.     }

  75.     public String nextKey() {
  76.         return encodeKeyNum(generateKeyNum(length, incrementSeq(), availableChars.length), chars);
  77.     }

  79.     private int incrementSeq() {
  80.         int oldSeq = seq++;

  82.         // Overflow, reset sequence number
  83.         if (seq > total) {
  84.             seq = 0;
  85.         }

  87.         return oldSeq;
  88.     }

  90.     // Sequence number mapper to make the end result looks random
  91.     // Original remap formula: total / partition * (seq % partition) + (int) Math.floor(seq / partition)
  92.     // will generate many repetitive character pattern for a range of sequence numbers which is not ideal.
  93.     public int remap(int num, int length, int base) {
  94.         int v = num;
  95.         int[] vals = new int[length];

  97.         for (int i = 0; i < vals.length; i++) {
  98.             vals[i] = v % base;

  100.             v = (v - vals[i]) / base;

  102.             if (i > 0) {
  103.                 vals[i] = (vals[0] + vals[i] + i) % base;
  104.             }
  105.         }

  107.         // Key can be generated directly from here.
  108.         int result = 0;

  110.         for (int i = 0; i < vals.length; i++) {
  111.             result += vals[i] * Math.pow(base, i);
  112.         }

  114.         return result;
  115.     }

  117.     private String encodeKeyNum(int keyNum, char[][] chars) {
  118.         char[] keyChars = new char[length];

  120.         for (int i = 0; i < keyChars.length; i++) {
  121.             keyChars[keyChars.length - i - 1] =
  122.                 chars[i][keyNum / ((int) Math.pow(chars[i].length, i)) % chars[keyChars.length-1].length];
  123.         }

  125.         return new String(keyChars);
  126.     }

  128.     private int generateKeyNum(int l, int s, int base) {
  129.         return remap(s, l, base);
  130.     }
  131. }
複製代碼
又多個 utility class 用




歡迎光臨 電腦領域 HKEPC Hardware (https://www.hkepc.com/forum/) Powered by Discuz! 7.2