ykmran

我諗最後樓主最後會死死氣自己係/dev/random拎32個byte

燕飛

回復 10 #chenathcx

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

其實用 LFSR 就solve 到

via HKEPC Reader for Android

winstercafe

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

一般確認 SMS 都只係六個位
有效時間控制嚮幾分鐘內
你既然唔係要 KEY
random 10萬個 combination 仲唔夠？

starone

你係咪想做 類似 short url o的Key ???

rabbit82047

講真條 key 要俾 user 用, 本身就應該有 table 裝住
你 random gen 條新 key 再同 existing key 對下就得
實際意義上 space cost = 0

3ldk

你係咪想做 類似 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

樓主要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

redeem code o個d唔需理會security既野一向用Hashids, 只要直接hash個auto increment 既id就得

chi251155

假設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

唔明點解唔 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 都係要撞