lcg線性同餘隨機數生成器

2021-03-04 星盟安全

作者: 人生若只如初見

計算機產生隨機數在概率算法設計中，隨機數分為真隨機數和偽隨機數，計算機只能產生偽隨機數。真隨機數：類似放射性元素的衰變等無法控制的且無法複製數據偽隨機數：通過較為容量大的數學公式產生的數字，具有可猜測性。在得到生成器的隨機數種子之後，可以通過計算得到偽隨機數序列。通用性偽隨機數生成器：s0=seed,s[i+1]=f(s[i])，推廣形式：s[i+1]=f(s[i],s[i-1],……,s[i-t])，其中t是固定整數。滿足通用性偽隨機數的推廣的例子，線性同餘生成器：s0=seed,s[i+1]=a*s[i]+b mod m,(i=0,1,2……)線性同餘生成器線性同餘序列的周期

1、存在遞推關係：x[i+1]=f(x[i])
2、其中的任意元素x[i]都在[0,m-1]範圍內
3、f(x)的值也在[0,m-1]範圍內

1、假設兩個集合s={0,1,2,3,……,m-2,m-1} size(s)=m
    T={} size(T)=0
    將產生的偽隨機數挪到集合T中
2、先生成第一個偽隨機數x1
    s={0,1,2,3,……,m-2,m-1} size(s)=m
    T={x1} size(T)=1
3、根據第一個偽隨機數x1生成第二個偽隨機數x2，判斷x2的歸屬，若x2屬於集合s則一個周期還未結束，若x2屬於集合T此處正好等於x1則一個周期產生，周期p=1

推論到x[i]即生成的每個x都屬於s，都轉移到T
此時：s={0,1,2,3,……,m-2,m-1} size(s)=m
      T={x1,x2,x3,……,x[i-2],x[i-1]} size(T)=i-1
若x[i]=f(x[i-1])∈s，則未能完成一周期
若x[i]=f(x[i-1])∈T，則已完成一個周期，周期p≤i-1

周期p也可能等於m，也就是最終s為空集，T中包含0到m-1的所有元素，且f(X[m])=x1
因此一定存在一個周期p≤m
推論：
    1) 當周期p＜m時，選取不同的隨機數種子也就是x0(初始值)產生的周期可能會不同。
    2) 當周期p=m時，序列的周期與初始值x0無關，周期必定為p。

參數選擇m的選擇一般來說，模數應該儘可能大，這樣可以產生較長的周期，常見的模數挑選一般為2**w（常用的為2^32或者2^64，產生結果直接截斷最右邊的32bit或者64bit）當模數為2**w的時候，最後產生未模之前的數字與最後的結果相比，是該數字的比特位向右邊減w位的結果，這種形式在低位上的隨機性並不是很好。可以在產生隨機數後截取高位比特，將隨機性不好的低位比特直接捨棄。a的選擇（0≤a<m）a的取值會很大程度上影響整個生成器的安全性，應該使周期儘量長（最長為m），但是周期長的序列隨機性比較差。當a=1時，生成器的公式為s[i+1]=s[i]+b mod m當a=0時，生成器的公式為s[i+1]=b mod m，安全性為0.當a取值其他數字時，影響隨機數生成器生成數字的周期。選取參數的總結當m選取為2的冪次方時，應該滿足a mod 8=5當m和a選取都合理時，b需要在與m互質的條件下選取。最大周期符合的條件：例題根據線性同餘生成器lcg可得：lcg=(a*x+c)%m根據題目，當輸入數字時，可以得到多個連續隨機數，根據偽隨機數生成的機制，可以了解到，隨機數的生成只要知道隨機數種子就可以破解類推到線性同餘方程組，也就是說當知道a,c,m時即可知道隨機數的整個序列例如：假設我們知道lcg0,那麼lcg1=(alcg0+c)%m,同理lcg2=(alcg1+c)%m此時我們隨意提交多次，可以從中得到連續的隨機數，類比於lcg0,lcg1,lcg2的關係lcg0=32081 lcg1=23815 lcg2=1237 lcg3=2387爆破模數module，每次moudle值改變時，都進行下面的操作：

lcg1=(a*lcg0+c)%m       lcg2=(a*lcg1+c)%m

兩式相減   左邊為:lcg2-lcg1   右邊為:(a*lcg1+c)-(a*lcg0+c)

化簡為: [lcg2-lcg1=a*(lcg1-lcg0) ] %m

根據求餘運算規則可知  
[a=(lcg2-lcg1)*gmpy2.invert(lcg1-lcg0,m)]%m

此時代入lcg0,lcg1,lcg2之後可求得a

代入lcg1=(a*lcg0+c)%m,把c當作未知數放到等式左邊後，式子為：
c=[lcg1-(a*lcg0)]%m

類推lcg3_guess=(a*lcg2+c)%m
將求得地lcg3_guess與lcg3比較，如果相等，證明求得的a,c,m為正確值
否則，m=m+1，繼續驗證

注意：
1、這個式子成立條件是兩邊同時對m求餘
2、gmpy2.invert(x1,x2)是求與x1%x2同餘的最小數，二者在求餘操作後等價，因為餘數相等，該式表示餘數，類似7%5=2%5

求得正確的a,c,m之後，線性同餘方程為 lcg[i]=(a*lcg[i-1]+c)%m

相關焦點

  • 密碼學的骰子——隨機數
    根據一般定義，隨機數應該具有以下三個性質：隨機性，不存在統計學偏差，是完全雜亂的數列，即分布均勻性和獨立性；不可預測性，不能從過去的隨機數數列推測出下一個出現的數；不可重現性，不能重現相同的數列。我們在平時編程開發裡用到的隨機數，一般都只滿足第一個條件，這種只滿足隨機性分布的隨機數，就叫做偽隨機數或弱偽隨機數。這是因為程式語言提供的隨機數生成方法（學名叫偽隨機數生成器）是靠軟體算法實現的，既然是算法，那就必定遵循了一定的規律，也就有被預測的可能。
  • 前官員修改隨機數生成器操縱彩票中獎號碼
    （原標題：前官員修改隨機數生成器操縱彩票中獎號碼）
  • python安全開發軍規之四:使用安全的隨機數生成器
    背景日常開發中，必然會碰到需要生成隨機數的需求，比如生成圖片驗證碼，簡訊驗證碼……隨機數生成既然是這麼簡單的一個功能，開發必然也很簡單，我們看看怎麼生成一個隨機數，這裡以隨機生成1-100的整數為例。普通程式設計師的寫法import randomrandom.randint(1,100)只用了兩行代碼，程式設計師小Z就寫出了一個隨機數。QA有話說隨機模塊提供的隨機生成器是偽隨機數生成器。所謂偽隨機數，是通過固定的算法生成的，其結果是確定的，可預見的。
  • java生成隨機數的五種方法
    initRNG() 方法是 synchronized 的，因此在多線程情況下，只有一個線程會負責創建偽隨機數生成器（使用當前時間作為種子），其他線程則利用該偽隨機數生成器產生隨機數。因此 Math.random() 方法是線程安全的。
  • Java 生成隨機數的 5 種方式,你知道幾種?
    方法是 的，因此在多線程情況下，只有一個線程會負責創建偽隨機數生成器（使用當前時間作為種子），其他線程則利用該偽隨機數生成器產生隨機數。Java生成隨機數的幾種高級用法，這篇推薦看一下。 因此 方法是線程安全的。
  • 下一代Tor通信將用分布式隨機數生成器加密
    當前，由於TOR（洋蔥網絡）的通信安全性不斷受到挑戰，TOR項目團隊開始為下一代的洋蔥路由網絡尋找新的加密途徑，例如在隨機數字的生成方面。TOR項目團隊開始為下一代的洋蔥路由網絡尋找新的加密途徑　　在通信安全領域，由於要生成隨機、不可預測的加密密鑰，因此對於隨機數的應用是必不可少的。
  • 隨機數大家都會用,但是你知道生成隨機數的算法嗎?
    再不濟我們每周的抽獎都是用隨機數抽出來的，我們用隨機數的時候，往往都會加一個前綴，說它是偽隨機數，那麼這個偽隨機數的偽字該怎麼解釋，什麼又是真隨機數呢？計算機算法得出的各種隨機數之所以是偽隨機數是因為它們的結果都是可以預測的，只要我們知道算法和起始狀態以及各種參數，就可以預測下一次隨機出來的結果。而真隨機數則無法預測，就是純粹隨機的。但問題來了，拋硬幣和擲骰子這些物理現象又是真的隨機嗎？如果我們知道了硬幣的起始狀態以及拋擲的角度和力度，是不是可以預測硬幣拋擲的結果呢？
  • 隨機數生成
    如利用蒙特卡羅法估計測量數據的不確定時，就需要使用隨機數生成器來傳遞分布。本書中大量的例子都用到了示例數據，創建這些數據就利用了隨機數生成器。Igor具有強大的統計分析功能，提供了大量函數和命令，用於分布計算、參數估計、假設檢驗、回歸分析等。其中僅偽隨機數生成器就有12種，可以生成滿足常見分布要求的隨機數，如二項分布隨機數、均勻分布隨機數、高斯分布隨機數、洛倫茲分布隨機數等。
  • 普林斯頓計算機教授炮轟「偽AI」:精心炮製的隨機數生成器罷了
    數百萬求職者面對的不過是精心設計的隨機數生成器。令人懷疑的，還遠不只是這一種產品。為了讓大家不被這樣的最新「智商稅」收割，阿文德決心教會大家如何識別這些AI界的騙子們。他的這份「防騙指南」登場數小時，就已經在推特上收穫了1500贊。
  • 數與代數---同餘問題
    四個自然數：2836，4582，5164，6522分別除以同一個兩位數的自然數，所得的餘數相同，則這個除數是（          ）。
  • 簡要解析:Java中隨機數生成的代碼實現
    double rand = Math.random();        通過Random類的對象　　程序可生成許多不同類型的隨機數字，做法很簡單，只需調用方法nextInt()和nextFloat()即可(也可以調用nextLong()或者nextDouble())。
  • matlab生成隨機數函數的20多個命令,你知道多少?「肥波貓」
    「肥波貓」rand(n):生成0到1之間的n階隨機數方陣 rand(m,n):生成0到1之間的m×n的隨機數矩陣 (現成的函數)betarnd 貝塔分布的隨機數生成器 binornd 二項分布的隨機數生成器
  • 密碼學基礎——偽隨機數生成器
    獵豹區塊鏈中心在密碼學起源的科普文章中，給大家介紹了經典的加密方法，從凱撒密碼到多表密碼，以及一次一密，在本篇文章中，我們將會和大家分享最早實現一次一密的加密機以及偽隨機數生成器。偽隨機數生成器在理解偽隨機數之前，我們先來看看真正的隨機數，我們的物理世界，其實到處都存在著隨機波動，通過測量被稱為噪音的隨機波動，我們可以生成真正的隨機數，測量噪音的過程被稱為取樣，我們可以通過取樣得到某個隨機數字。
  • Chrome修復JS引擎隨機數沒那麼隨機的問題
    小編正用著呢~在過去幾年裡，許多人研究都發現Chrome瀏覽器的V8 JavaScript引擎在用Math.random()函數的時候返回的隨機數沒有那麼隨機。今天這個問題已經解決了，即在最新版的Chrome 49中——很快這個版本就會發布。Math.random()是在JavaScript中達成隨機性的最常用的方式，這對許多web應用而言是比較重要的組成部分。
  • 製作Excel隨機姓名生成器,解放你的雙手
    今天我們就利用Excel來製作簡單易用且高效的隨機姓名生成器，生成幾百上千個姓名只需點一下滑鼠那麼簡單！首先我們在網上或其它途徑找到大量的姓名，越多越好，網上有許多，很多Excel格式的成員名單都可以在網上找到，這裡我們通過各種途徑收集了430個三個字以內的姓名，如圖將它們全部放在了A列。第一步，將每個姓名逐字拆分。
  • 同餘定理
    這一期，我們來學習同餘定理。「同餘」這個概念最初是由德國數學家高斯發明的，在數學上，尤其是數論上，有著非常廣泛的應用。首先我們還是從例題講起。
  • 「名單公布」北海市市直幼兒園、義務教育學校電腦隨機抽錄名單公布
    為公平、公正、公開做好市直幼兒園、義務教育學校招生工作，8月3日，北海市教育局組織開展市直幼兒園、義務教育學校電腦隨機抽籤招生錄取工作在西北師範大學北海附屬中學報告廳順利舉行期待已久小朋友們，同學們快來康康下學期有哪些新夥伴吧2020年北海市直學校電腦隨機抽籤擬錄取名單公示
  • 揭開密碼的神秘面紗——同餘運算 Part IV
    在之前的三篇文章中(1、2、3)我們介紹了密碼學的主要部分——同餘運算的基本內容，了解了什麼是同餘運算，等價關係，模的加減乘除運算以及冪運算，歐幾裡得算法等等，本章中我們將會把密碼學與同餘運算兩者結合起來，探索同餘運算是怎樣運用到密碼學中的。密碼學的起源想像一下,Alice 和 Bob 兩個人要遠距離的分享了一個重要的秘密。
  • 【Geometric GAN】引入線性分類器SVM的Geometric GAN
    McGAN在訓練過程中，特徵空間包括三種幾何操作：（1）分類超平面搜索：尋找線性分類器的分類超平面。（2）判別器向遠離分類超平面方向更新：判別器參數利用隨機梯度下降方法（SGD）向遠離分類超平面方向更新。（3）生成器朝向分類超平面方向更新：生成器參數利用隨機梯度下降方法（SGD）沿分類超平面法向量方向更新。