隱藏信息檢測與還原技術-中國科學技術大學培訓資料

1、隱藏信息檢測與還原技術-中國科學技術大學Ch.1 緒論緒論1. 故事：想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點。經(jīng)分析你能確定最有可能的兩個地點是藏寶地點，但二者相距甚遠。假設你如果已到達其中一處，就立即知道該處是否為藏寶地點。你到達兩處之一地點及從其中一處到另一處的距離是5天的行程。進一步假設有一條惡龍，每晚光顧寶藏并從中拿走一部分財寶。假設你取寶藏的方案有兩種：1.1 引言引言 方案1. 花4天的時間計算出準確的藏寶地點，然后出發(fā)尋寶，一旦出發(fā)不能重新計算 方案2. 有一個小精靈告訴你地圖的秘密，但你必須付給他報酬，相當于龍3晚上拿走的財寶 Prob

2、1.1.1 若忽略可能的冒險和出發(fā)尋寶的代價，你是否接受小精靈的幫助？ 顯然，應該接受小精靈的幫助，因為你只需給出3晚上被盜竊的財寶量，否則你將失去4晚被盜財寶量。 但是，若冒險，你可能做得更好！1.1 引言引言 設x是你決定之前當日的寶藏價值，設y是惡龍每晚盜走的寶藏價值，并設x9y 方案1：4天計算確定地址，行程5天，你得到的寶藏價值為：x-9y 方案2：3y付給精靈，行程5天失去5y，你得到的寶藏價值為：x-8y 方案3：投硬幣決定先到一處，失敗后到另一處(冒險方案) 一次成功所得：x-5y，機會1/2 二次成功所得：x-10y，機會1/21.1 引言引言期望贏利：期望贏利：x-7.5y

3、2. 意義 該故事告訴我們：當一個算法面臨某種選擇時，有時隨機選擇比耗時做最優(yōu)選擇更好，尤其是當最優(yōu)選擇所花的時間大于隨機選擇的平均時間的時侯 顯然，概率算法只能是期望的時間更有效，但它有可能遭受到最壞的可能性。3. 期望時間和平均時間的區(qū)別v 確定算法的平均執(zhí)行時間 輸入規(guī)模一定的所有輸入實例是等概率出現(xiàn)時，算法的平均執(zhí)行時間。v 概率算法的期望執(zhí)行時間 反復解同一個輸入實例所花的平均執(zhí)行時間。 因此，對概率算法可以討論如下兩種期望時間n 平均的期望時間：所有輸入實例上平均的期望執(zhí)行時間n 最壞的期望時間：最壞的輸入實例上的期望執(zhí)行時間4. 例子n快速排序中的隨機劃分要求學生寫一算法，由老師

4、給出輸入實例，按運行時間打分，大部分學生均不敢用簡單的劃分，運行時間在1500-2600ms，三個學生用概率的方法劃分，運行時間平均為300ms。n8皇后問題系統(tǒng)的方法放置皇后(回溯法)較合適，找出所有92個解 O(2n)，若只找92個其中的任何一個解可在線性時間內完成O(n)。 隨機法：隨機地放置若干皇后能夠改進回溯法，特別是當n較大時n判斷大整數(shù)是否為素數(shù)確定算法無法在可行的時間內判斷一個數(shù)百位十進制數(shù)是否素數(shù)，否則密碼就不安全。 概率算法將有所作為：若能接受一個任意小的錯誤的概率5. 概率算法的特點 (1) 不可再現(xiàn)性 在同一個輸入實例上，每次執(zhí)行結果不盡相同，例如n N-皇后問題概率算

5、法運行不同次將會找到不同的正確解n 找一給定合數(shù)的非平凡因子每次運行的結果不盡相同，但確定算法每次運行結果必定相同 (2) 分析困難 要求有概率論，統(tǒng)計學和數(shù)論的知識6. 約定 隨機函數(shù)uniform：隨機，均勻，獨立n 設a，b為實數(shù)，ab, uniform(a, b) 返回x，a x b 設i，j為整數(shù)，ij, uniform(i, j)=k, i k j 設X是非空有限集， uniform(X) X 例1：設p是一個素數(shù)，a是一個整數(shù)滿足1a0 do if (j is odd) s sa mod p;a a2 mod p;j j div 2;return s;Draw (a, p) /

6、在X中隨機取一元素j uniform(1.p-1);return ModularExponent(a, j, p); / 在X中隨機取一元素n 偽隨機數(shù)發(fā)生器在實用中不可能有真正的隨機數(shù)發(fā)生器，多數(shù)情況下是用偽隨機數(shù)發(fā)生器代替。大多數(shù)偽隨機數(shù)發(fā)生器是基于一對函數(shù)：S: X X, 這里X足夠大，它是種子的值域R: X Y, Y是偽隨機數(shù)函數(shù)的值域使用S獲得種子序列：x0=g, xi=S(xi-1), i0然后使用R獲得偽隨機序列：yi=R(xi), i 0該序列必然是周期性的，但只要S和R選的合適，該周期長度會非常長。TC中可用rand()和srand(time), 用GNU C更好n 基本特征

7、隨機決策在同一實例上執(zhí)行兩次其結果可能不同在同一實例上執(zhí)行兩次的時間亦可能不太相同n 分類Numerical, Monte Carlo, Las Vegas, Sherwood.很多人將所有概率算法(尤其是數(shù)字的概率算法)稱為Monte Carlo算法1.2 概率算法的分類概率算法的分類n 數(shù)字算法隨機性被最早用于求數(shù)字問題的近似解例如，求一個系統(tǒng)中隊列的平均長度的問題，確定算法很難得到答案概率算法獲得的答案一般是近似的，但通常算法執(zhí)行的時間越長，精度就越高，誤差就越小使用的理由 現(xiàn)實世界中的問題在原理上可能就不存在精確解例如，實驗數(shù)據(jù)本身就是近似的，一個無理數(shù)在計算機中只能近似地表示 精確解

8、存在但無法在可行的時間內求得有時答案是以置信區(qū)間的形式給出的1.2 概率算法的分類概率算法的分類n Monte Carlo算法 (MC算法)蒙特卡洛算法1945年由J. Von Neumann進行核武模擬提出的。它是以概率和統(tǒng)計的理論與方法為基礎的一種數(shù)值計算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計算，二是用偽隨機數(shù)模擬真正的隨機變量的樣本。這里我們指的MC算法是： 若問題只有1個正確的解，而無近似解的可能時使用MC算法例如，判定問題只有真或假兩種可能性，沒有近似解 因式分解，我們不能說某數(shù)幾乎是一個因子n 特點：MC算法總是給出一個答案，但該答案未必正確，成功(即答案是正確的)的概

9、率正比于算法執(zhí)行的時間n 缺點：一般不能有效地確定算法的答案是否正確1.2 概率算法的分類概率算法的分類n Las Vegas算法 (LV算法)LV算法絕不返回錯誤的答案。n 特點：獲得的答案必定正確，但有時它仍根本就找不到答案。 和MC算法一樣，成功的概率亦隨算法執(zhí)行時間增加而增加。無論輸入何種實例，只要算法在該實例上運行足夠的次數(shù)，則算法失敗的概率就任意小。 Sherwood算法Sherwood算法總是給出正確的答案。當某些確定算法解決一個特殊問題平均的時間比最壞時間快得多時，我們可以使用Sherwood算法來減少，甚至是消除好的和壞的實例之間的差別。1.2 概率算法的分類概率算法的分類這

10、類算法主要用于找到一個數(shù)字問題的近似解2.1 值計算n實驗：將n根飛鏢隨機投向一正方形的靶子，計算落入此正方形的內切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點的概率相等(用計算機模擬比任一飛鏢高手更能保證此假設成立)設圓的半徑為r，面積s1= r2； 方靶面積s2=4r2由等概率假設可知落入圓中的飛鏢和正方形內的飛鏢平均比為：由此知： Ch.2 數(shù)字概率算法數(shù)字概率算法2244krnr4 /4nk n kn求近似值的算法為簡單起見，只以上圖的右上1/4象限為樣本Darts (n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1); / 隨

11、機產(chǎn)生點(x,y)if (x2 + y2 1) then k+; /圓內return 4k/n;實驗結果： =3.141592654n = 1000萬: 3.140740, 3.142568 (2位精確)n = 1億: 3.141691, 3.141363 (3位精確)n = 10億: 3.141527, 3.141507 (4位精確)2.1 值計算值計算n 求近似值的算法Ex.1 若將y uniform(0, 1) 改為 y x, 則上述的算法估計的值是什么？2.1 值計算值計算Monte Carlo積分(但不是指我們定義的MC算法)n概率算法1設f: 0, 1 0, 1是一個連續(xù)函數(shù)，則由

12、曲線y=f(x), x軸, y軸和直線x=1圍成的面積由下述積分給出：向單位面積的正方形內投鏢n次，落入陰影部分的鏢的數(shù)目為k，則顯然，只要n足夠大2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)10( )Sf x dx/1kSSk nn/Sk n n概率算法1HitorMiss (f, n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1);if y f(x) then k+;return k/n;Note: 是S/4的面積， =S, 2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)1201x dx12041x dxn

13、 概率算法1Ex2. 在機器上用 估計值，給出不同的n值及精度。Ex3. 設a, b, c和d是實數(shù)，且a b, c d, f:a, b c, d是一個連續(xù)函數(shù)，寫一概率算法計算積分：注意，函數(shù)的參數(shù)是a, b, c, d, n和f, 其中f用函數(shù)指針實現(xiàn)，請選一連續(xù)函數(shù)做實驗，并給出實驗結果。2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)12041x dx( )baf x dxn概率算法1*Ex4. 設,是(0,1)之間的常數(shù)，證明：若I是 的正確值，h是由HitorHiss算法返回的值，則當n I(1-I)/2時有：Prob|h-I| 1 上述的意義告訴我們：Prob|h-I|

14、 , 即：當n I(1-I)/ 2時，算法的計算結果的絕對誤差超過的概率不超過，因此我們根據(jù)給定和可以確定算法迭代的次數(shù)解此問題時可用切比雪夫不等式，將I看作是數(shù)學期望。2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)10( )f x dx22(1)11(1)44IInII n概率算法2更有效的概率算法是： 在積分區(qū)間上隨機均勻地產(chǎn)生點，求出這些點上的函數(shù)值的算術平均值，再乘以區(qū)間的寬度：Crude (f, n, a, b) sum 0;for i 1 to n do x uniform(a, b);sum sum + f(x);return (b-a)sum/n;2.2 數(shù)字積分數(shù)

15、字積分 (計算定積分的值計算定積分的值)11( )()( ),nbiiaif x dxbaf xaxbnn 概率算法2用HitorMiss和Crude運行三次的結果為：假定 和 存在，由算法求得的估算值的方差反比于點數(shù)n。當n足夠大時，估計的分布近似為正態(tài)分布。對于給定的迭代次數(shù)n，Crude算法的方差不會大于HitorMiss的方差。但不能說，Crude算法總是優(yōu)于HitorMiss。因為后者在給定的時間內能迭代的次數(shù)更多。例如，計算值時，Crude需計算平方根，而用投鏢算法darts時無需計算平方根。2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)3.141855, 3.1414

16、22, 3.14143413.141662,3.141486, 3.141527hitncrude億( )baf x dx2( )bafx dxn確定的算法梯形算法將區(qū)間分為n-1個子區(qū)間，每個子區(qū)間內的長度為，Trapezoid (f, n, a, b) / 假設 n 2delta (b-a)/(n-1);sum (f(a) + f(b)/2;for x a+delta step delta to b delta dosum sum + f(x)return sum delta;2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)f(a)f(b)=f af a 22積分值( ( + )

17、+ ( +)+.+)n確定的算法 當n=100, =3.140399 當n=1,000, =3.141555 當n=10,000, =3.141586 當n=100,000, =3.141593一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于MC積分，但是n 有時確定型積分算法求不出解：例如， f(x)=sin2(100)! x)， 。 但是用梯形算法時，當2 n101時，返回值是0。若用MC積分則不會發(fā)生該類問題，或雖然發(fā)生，但概率小得多。2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)101( )2f x dx n 多重積分 在確定算法中，為了達到一定的精度，采樣點的數(shù)目隨著積分維

18、數(shù)成指數(shù)增長，例如，一維積分若有100個點可達到一定的精度，則二維積分可能要計算1002個點才能達到同樣的精度，三維積分則需計算1003個點。(系統(tǒng)的方法) 但概率算法對維數(shù)的敏感度不大，僅是每次迭代中計算的量稍增一點，實際上，MC積分特別適合用于計算4或更高維數(shù)的定積分。 若要提高精度，則可用混合技術：部分采用系統(tǒng)的方法，部分采用概率的方法2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值) 上一節(jié)可以認為，數(shù)字概率算法被用來近似一個實數(shù)，本節(jié)可用它們來估計一個整數(shù)值。例如，設X為有限集，若要求X的勢|X|，則當X較大時，枚舉顯然不現(xiàn)實。n 問題：隨機選出25人，你是否愿意賭其中至少有

19、兩個人生日相同嗎？直覺告訴我們，一般人都不愿意賭其成立，但實際上成立的概率大于50%。2.3 概率計數(shù)概率計數(shù) 一般地，從n個對象中選出k個互不相同的對象，若考慮 選擇的次序，則不同的選擇有 種；若允許重復選取同 一對象，則不同的選法共有 種。 因此，從n個對象(允許同一對象重復取多次)中隨機均勻地選擇出的k個對象互不相同的概率是： ，注意a，b和b，a是不同的取法。由此可知，上述問題中，25個人生日互不相同的概率是：這里假設：不考慮潤年，一年中人的生日是均勻分布的。2.3 概率計數(shù)概率計數(shù)!()!nnkkn!()!knnkn25365!365,25340!365nk由Stirling公式知：

20、可得 假定 Tj;3.2 隨機的預處理隨機的預處理例2：離散對數(shù)計算離散對數(shù)計算困難使其可用于密碼算法，數(shù)字簽名等定義：設 a=gx mod p， 記 logg,pa=x，稱x為a的(以g為底模除p)對數(shù)從p，g，a計算x稱為離散對數(shù)問題。簡單算法： 計算gx對所有的x，最多計算0 x p-1 或 1xp，因為實際上離散對數(shù)是循環(huán)群； 驗證a=gx mod p 是否成立。dlog(g, a, p) / 當這樣的對數(shù)不存在時，算法返回p x 0; y 1; do x+; y y*g; / 計算y=gx while ( a y mod p) and (x p); return x3.2 隨機的預處

21、理隨機的預處理2,7xlog3x32 mod7例無解，不存在使問題：最壞O(p)循環(huán)次數(shù)難以預料，當滿足一定條件時平均循環(huán)p/2次當p=24位十進制數(shù)，循環(huán)1024次，千萬億次/秒 (1016次/秒) 大約算1年(108秒/年)若p是數(shù)百位十進制？隨機選擇都可能無法在可行的時間內求解。假設有一個平均時間性能很好，但最壞情況差的確定算法求logp,ga，怎樣用Sherwood算法求解該問題？設p=19, g=2當a=14, 6時，log2,1914 = 7, log2,196=14，即用dlog求14和6的離散對數(shù)時，分別要循環(huán)7和14次，執(zhí)行時間與a的取值相關。 用sherwood算法應該使得

22、與a無關，用隨機預處理的方法計算logg,pa3.2 隨機的預處理隨機的預處理定理(見p877, 31.6) dlogRH(g, a p) / 求logg,pa, a = gx mod p，求x / Sherwood算法 r uniform(0.p-2); b ModularExponent(g, r, p); /求冪模b=gr mod p c ba mod p; /(gr modp)(gxmodp)modp=gr+xmodp=c y logg,pc; / 使用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求xEx. 分析dlogRH的工作原理，

23、指出該算法相應的u和v3.2 隨機的預處理隨機的預處理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp隨機預處理提供了一種加密計算的可能性 假定你想計算某個實例x，通過f(x)計算，但你缺乏計算能力或是缺乏有效算法，而別人有相應的計算能力，愿意為你計算(可能會收費)，若你愿意別人幫你計算，但你不愿意泄露你的輸入實例x，你將如何做？可將隨機預處理使用到f的計算上： 使用函數(shù)u將x加密為某一隨機實例y 將y提交給f計算出f(y)的值 使用函數(shù)v轉換為f(x) 上述過程，他人除了知道你的實例大小外，不知道x的任何信息，因為u(

24、x,r)的概率分布(只要r是隨機均勻選擇的)是獨立于x的。3.2 隨機的預處理隨機的預處理 設兩個數(shù)組val1.n和ptr1.n及head構成一個有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：3.3 搜索有序表搜索有序表:ptri給個關鍵標非關鍵即關鍵出出下下一一字字的的下下if vali最if vali最大大字字0 if vali是0 if vali是最最大大字字 i 1 2 3 4 5 6 7vali 2 3 13 1 5 21 8ptri 2 5 6 1 7 0 3rank 2 3 6 1 4 7 5head=4 有序表：

25、有序表：1，2，3，5，8，13，21 n折半查找： 若val1.n本身有序，可用折半查找找某個給定的key，時間為O(lgn)。n順序查找：但此表為鏈式結構，故最壞時間是(n)。盡管如此，我們能夠找到一個確定性算法，平均時間為 。 相應的Sherwood算法的期望時間是 ，它雖然并不比確定性算法快，但他消除了最壞實例。 假定表中元素互不相同，且所求的關鍵字在表中存在，則給定x，我們是求下標i，使vali=x, 這里1i n。任何實例可以由兩個參數(shù)刻畫： 前n個整數(shù)的排列 x的rank3.3 搜索有序表搜索有序表()On()On設Sn是所有n!個排列的集合，設A是一個確定性算法 tA(n, k

26、, )表示算法A的執(zhí)行時間，此時間與被查找元素的秩k，以及val的排列相關。若A是一個概率算法，則tA(n, k, )表示算法的期望值。無論算法是確定的還是概率的，wA(n)和mA(n)分別表示最壞時間和平均時間，因此有： 3.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nAnnAASknw nt n kkn andSm ntn kn nknnSn的概率是，在 中每個排列的概率是時間為O(n)的確定算法n算法 設xvali且x在表中，則從位置i開始查找x的算法為：Search(x, i) /仍可改進while x vali do i

27、ptri;return i;在表val1.n中查找x的算法為：A(x) return Search(x, head);3.3 搜索有序表搜索有序表n 性能分析設rank(x)=k, 則： 算法A在n個元素的表中查找x所需的訪問數(shù)組元素的次數(shù)，顯然與無關 算法A最壞時的訪問次數(shù) 算法A平均的訪問次數(shù) 3.3 搜索有序表搜索有序表( , )Atn kw ( )Anm ( )An1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )AAnAAknNkn tn kknNknwnnnNknnmntn knT nO n 若時為最壞情況，此時設的概率相等，則綜上所述，時間為O(n)的

28、概率算法n算法 D(x) i uniform(1.n);y vali;case x y: return Search(x, ptri); / case2 otherwise: return i; / case3， x = y3.3 搜索有序表搜索有序表n性能分析(D訪問數(shù)組次數(shù)) 一般情況 設rank(x)=k, rank(vali)=j 若 k j, 則 ，屬于case2，從jth最小元之后搜索若 k = j, 則 ，屬于case3 最壞情況3.3 搜索有序表搜索有序表( , ) Dtn kk( , )-Dtn kkj( , )0Dtn kDDnN,w (n)?j 1,knSearchn-1w (n)n 1 當時，執(zhí)行次數(shù)為， 平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnn