有單向、雙向、三向3種認證方式，前兩者必須檢查時間戳以防重放攻擊，單向因為只有一個消息傳遞，如果僅靠一次性隨機數(shù)是無法判斷消息是否重放。雙向有兩個消息傳遞，一來一回，僅靠一次性隨機數(shù)只能檢測到發(fā)響應(yīng)那方的重放。最后者則不必，可僅通過一次性隨機數(shù)檢測自己是否遭遇重放攻擊，因為接收第二個消息的那方，通過判斷第二個消息中隨機數(shù)是否等于自己先前已發(fā)送第一個消息中的那個，若不等于則為重放，若等于則發(fā)第三個確認消息給對方，對方收到并判斷確認消息中的隨機數(shù)是否等于先前它已發(fā)送第二個消息中的隨機數(shù)，若等于則說明第它收到的第一個消息的確是另一方發(fā)送的即非重放，否則為重放。因此三向認證可不必同步雙方時鐘。但正因為不強制檢查時間戳而可能導(dǎo)致
中間人攻擊：假設(shè)通信雙方為A、B，中間人為C，攻擊步驟如下
1. C與B認證時，發(fā)送先前已截獲的A到B請求消息給B
2. 截獲并存儲B到A的響應(yīng)消息x，但不轉(zhuǎn)發(fā)，開始與A認證
3. 收到A的請求消息后，解密x取出其中的隨機數(shù)Rb作為響應(yīng)給A消息中的隨機數(shù)，用自己私鑰簽署整個消息后發(fā)給A
4. 收到并轉(zhuǎn)發(fā)A的確認消息給B
以上完成后，C就能冒充A與B通信了。一種簡單的改進方法是先用對方的公鑰加密消息中的隨機數(shù)，再用自己的私鑰簽署整個消息。關(guān)于網(wǎng)絡(luò)協(xié)議的安全性分析，主流方法是形式化分析，可以借助相關(guān)工具來驗證找出漏洞
posted @
2023-09-30 08:00 春秋十二月 閱讀(436) |
評論 (0) |
編輯 收藏
1.
對于RSA，給定大整數(shù)n分解的一對素因子p和q，p或q是否素數(shù)決定不了安全性，但決定算法的正確性，也就是說p或q不能為合數(shù)，而安全性取決于n的位數(shù)及p、q的距離，n越大則難于素因子分解（因為素數(shù)測試是一個P問題，而因子分解是一個NP問題，其耗時是關(guān)于n的指數(shù)），|p - q|要大是為抵抗一種
特殊因子分解攻擊，論證如下：由(p+q)
2/4 - n = (p+q)
2/4 - pq = (p-q)
2/4，若|p - q|小，則(p-q)
2/4也小，因此(p+q)
2/4稍大于n，(p+q)/2稍大于n
1/2即根號n。可得n的如下分解法：a) 先順序檢查大于n
1/2的每一整數(shù)x，直至找到一個x使得x
2 - n是某一整數(shù)y的平方；b) 再由x
2 - n = y
2 得 n = (x+y)(x-y)。另外，p - 1和q - 1都應(yīng)有大素因子（所有因子皆是大素數(shù)），以抵抗可能的
重復(fù)加密攻擊（重復(fù)加密較少步后可恢復(fù)出明文）
2.
對于DH密鑰交換，通常選擇階為素數(shù)的有限循環(huán)(子)群，這時素數(shù)決定了安全性。因素數(shù)不能再因子分解，故避免了針對階為合數(shù)的質(zhì)因子分解且利用中國剩余定理求離散對數(shù)的(已知最好)攻擊。具體講就是為了防
index-calculus方法求解離散對數(shù)，底層循環(huán)群G的素數(shù)模p要足夠大，長度1024位可實現(xiàn)80位安全等級，長度3072位可實現(xiàn)128位安全等級；另為了防
Pohlig-Hellman攻擊，G的階p-1必須不能因式分解為全部都是小整數(shù)的素數(shù)因子，且為了p-1的每個因子構(gòu)成的子群防
baby-step giant-step或
Pollards's rho攻擊，要求對80位安全等級而言，p-1的最小素因子必須至少為160位，而對128位安全等級，其至少為256位
3.
對于Hash函數(shù)，安全性要求有三點：第一是單向性，由于壓縮函數(shù)理論上存在碰撞，因此單向性是指計算不可行，為什么要單向性？因為若不單向，則可從結(jié)果比如簽名逆出原文消息；第二是抗弱沖突性即
第1類生日攻擊，計算不可行；第三是抗強沖突性即
第2類生日攻擊，計算不可行。這三點要求，取決于壓縮函數(shù)是否能抗差分、線性等密碼分析
4. 周知
Shamir門限方案基于多項式的拉格朗日插值公式，普遍的設(shè)計采用GF(q)域上的多項式，秘密s為f(0)，q是一個大于n的大素數(shù)（n是s被分成的部分數(shù)）。正常來講，參與者個數(shù)必須至少是設(shè)計時的k，才能恢復(fù)出正確的s。如果個數(shù)少于k比如k-1，則只能猜測s0=f(0)以構(gòu)建第k個方程，那么恢復(fù)得到的多項式g(x)等同設(shè)計時的多項式f(x)的概率是1/q。因為g(x)的項系數(shù)可以看作關(guān)于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q為素數(shù)，故依模剩余系遍歷定理，當s0取GF(q)一值時，則h(s0)唯一對應(yīng)另一值。所以h(s0)等于f(0)的概率為1/q。由此可見，當q取80位以上，敵手攻擊概率不大于1/2
80，這已經(jīng)很低了。這種門限方案如同RSA加密，再次佐證了素數(shù)越大安全性越高
5.
PGP是密碼學(xué)經(jīng)典應(yīng)用，體現(xiàn)在首先支持保密與認證業(yè)務(wù)的正交，即獨立或組合，且組合時按認證、壓縮、加密的順序，這個順序是經(jīng)考究有優(yōu)勢的；其次會話密鑰是一次性的，由安全偽隨機數(shù)生成器生成，且按公鑰加密；最后使用自研的密鑰環(huán)與信任網(wǎng)解決公鑰管理問題。理論本質(zhì)上，PGP提供的是一種保密認證業(yè)務(wù)的通用框架，因為具體的對稱加密算法、隨機數(shù)生成、公鑰算法，都可依需要靈活選配擴展。PGP有兩個問題跟組合與概率相關(guān)，一個是算密鑰環(huán)N個公鑰中，密鑰ID(64位)至少有兩個重復(fù)的概率？設(shè)所求概率為p，先算任意兩個不重復(fù)的概率q，令m=2
64，則q=m!/((m-N)!*m
N)，則p=1-q，不難看出，N越小則q越大則p越小，因?qū)嶋H應(yīng)用N<<m，故p非常小可忽略，即PGP取公鑰中最低64有效位作密鑰ID，是可行的。另一個是簽名摘要暴露了前16位明文，對哈希函數(shù)安全的影響有多大？這問題意思應(yīng)該是敵手拿到消息后但沒發(fā)送方的私鑰作簽名，只能窮舉變換原消息并求哈希值，使之與消息摘要剩余位組相等。這本質(zhì)是求
兩類生日攻擊碰撞概率大于0.5時所需的輸入量。在僅認證模式中，抗弱碰撞計算量降低為原來的1/2
16，抗強碰撞計算量至少降低為原來的1/2
8。另外，考慮到這16位明文可能的特殊性，有沒更快的代數(shù)攻擊，需進一步研究
posted @
2023-09-28 08:04 春秋十二月 閱讀(3022) |
評論 (0) |
編輯 收藏posted @
2023-09-26 16:47 春秋十二月 閱讀(2149) |
評論 (0) |
編輯 收藏
周知編譯原理龍書闡述的基本塊指令調(diào)度算法，它所使用的空的資源預(yù)約表RTD與每個指令的資源預(yù)約表RT，可以看作二維矩陣，行表示時鐘周期、列表示cpu資源，其定位的元素值1表示占用/預(yù)約，0表示空閑/非預(yù)約。前者是隨周期遞增而動態(tài)擴大的矩陣，后者是固定尺寸(維數(shù))的矩陣（指令花費周期與每周期預(yù)約資源皆已知）。在調(diào)度時，按帶優(yōu)先級比如關(guān)鍵路徑的拓撲排序基本塊內(nèi)的指令，順序選取一條指令I(lǐng)nst，計算每前驅(qū)發(fā)射周期加延遲的結(jié)果tmp，取所有tmp的最大值tmax作為Inst的發(fā)射周期，再判斷處理器資源是否可用，即RTD和RT作
與運算，得到一個新矩陣RTN，若RTN為
全零矩陣則tmax為Inst的最終發(fā)射周期，否則遞增tmax再做矩陣與運算，直至得到全零矩陣。最后更新RTD，即RTD與RT作
或運算結(jié)果存于RTD。重復(fù)上述過程直到基本塊末尾。
綜上不難看出，如果一個基本塊很大比如有1000條指令，平均每指令花2個周期，則RTD需要2000個條目，若一條目即矩陣每行占用32字節(jié)（256種資源數(shù)），則總量約64k。當然這對于現(xiàn)代內(nèi)存體量來說不算什么，但可以有更好的節(jié)省內(nèi)存的做法：RTD尺寸其實可以相對固定，其上限為基本塊中耗費周期最多指令的周期的一個大于1常數(shù)因子倍（為兼顧指令并行性），這樣一來就要增加當指令完成時（當前指令發(fā)射周期大于前一條的終止周期時復(fù)位前一條指令的RTD）從發(fā)射周期處復(fù)位RTD即作一個矩陣反運算的操作，其它步驟對應(yīng)的矩陣與、矩陣或運算的操作保留不變。另由于RTD固定了尺寸，因此發(fā)射周期遞增后要取模
【備注】以上是我針對簡單機器模型（每種資源數(shù)量僅一個，比如整數(shù)運算單元1個，內(nèi)存訪問單元1個，浮點運算單元1個）用布爾矩陣作的優(yōu)化。如果是復(fù)雜的超標量機器即每種資源數(shù)有多個，那么只需修改如下：布爾矩陣換成整數(shù)矩陣；新增一個機器資源可用總數(shù)整數(shù)矩陣RDA（單列資源數(shù)同值），布爾矩陣與運算換成加法并與RDA比較，若大于RDA則遞增tmax；布爾矩陣或運算換成加法；布爾矩陣反運算換成減法，RTD減RT存于RTD
posted @
2023-09-23 12:14 春秋十二月 閱讀(351) |
評論 (0) |
編輯 收藏曾因朋友問到監(jiān)控，致使我探究了kretprobe的實現(xiàn)，想到編譯中的尾調(diào)用優(yōu)化，作個小結(jié)
?1. kretprobe_trampoline_holder該跳轉(zhuǎn)函數(shù)無參是必須的或說最好的通用設(shè)計，因為替換返回地址是非正常程序流程，即被探測函數(shù)的調(diào)用者無感知，不存在為跳轉(zhuǎn)函數(shù)準備入?yún)ⅰＨ粢O(shè)計傳參且只讀，則不會破壞被探測函數(shù)調(diào)用者的上下文，但跳轉(zhuǎn)函數(shù)內(nèi)部流程怎么用參數(shù)是個問題，這需要一種約定
?2. 跳轉(zhuǎn)函數(shù)為調(diào)用trampoline_handler準備入?yún)ⅲ丛跅Ｉ蠘?gòu)造一個（不完整的）pt_regs，再把它地址即棧頂賦給rdi，rdi是x86_64上傳入第一參數(shù)使用的寄存器，同時預(yù)留一個棧單元存放原返回地址（為什么要預(yù)留？因為被探測函數(shù)返回時，其調(diào)用者存放返回地址的棧空間被釋放了，所以得在跳轉(zhuǎn)函數(shù)內(nèi)造一個）。由于trampoline_handler內(nèi)調(diào)到用戶自定義handler而傳入pt_regs，因此自定義handler內(nèi)要注意最好別改動pt_regs，否則會破壞被探測函數(shù)調(diào)用者的上下文
posted @
2023-09-13 02:26 春秋十二月 閱讀(339) |
評論 (0) |
編輯 收藏有理數(shù)域的本原多項式與有限域的本原多項式定義不同，前者不要求不可約（由高斯引理知兩個本原多項式的乘積還是本原），后者則必須不可約（確保生成的有限域其每個元素有逆元）。aes基于有限域F{0,1}設(shè)計，故使用的模8次多項式不可約
P(x)=x^8+x^4+x^3+x+1，但不是本原多項式，因為它的階是51而非255。有限域次數(shù)為8的本原多項式有16個、不可約多項式有30個（由莫比烏斯反演推出），具體多項式影響s盒與列混合操作的實現(xiàn)。不可約加之0的逆元規(guī)定為0，保證正確加解密。若0的逆元規(guī)定為非0比如x，則導(dǎo)致x有兩個逆元，便違反了逆元唯一性，除非s盒不用有限域設(shè)計。逆元等于其自身的非0元素只有1，原因可類比模素數(shù)二次剩余的求解
posted @
2023-09-13 02:00 春秋十二月 閱讀(379) |
評論 (0) |
編輯 收藏1. 若DFA D是用子集構(gòu)造法從NFA N構(gòu)造出來的，則L(D)=L(N)
2. 一個語言L被某個DFA接受，當且僅當被某個NFA接受
3. 一個語言L被某個£-NFA接受，當且僅當被某個DFA接受
4. 若對于某個DFA A，L=L(A)，則存在一個正則表達式R使得L=L(R)
5. 每一個用正則表達式定義的語言也可用有窮自動機定義
6. 若通過填表算法不能區(qū)分兩個狀態(tài)，則它們是等價的
7. DFA的狀態(tài)等價性是傳遞的
8. 若對于DFA每個狀態(tài)q及與q等價的所有狀態(tài)組成塊，則不同的狀態(tài)塊形成狀態(tài)集合的劃分。也就是說，每個狀態(tài)恰好屬于一個塊，同一塊中的所有成員都是等價的，從不同塊中選擇的狀態(tài)對都不是等價的
9. 根據(jù)等價狀態(tài)劃分算法最小化DFA D得到的DFA M是唯一的。也就是說，不存在其它等價于D的DFA N，其狀態(tài)數(shù)比M少
----------------------------------------------------------------------------------------
10. 對于正則表達式，空集是并運算的單位元、連接運算的零元，空串是連接運算的單位元
11. 若L和M都是正則語言，則L和M的并、交、差也是
12. 若L是字母表T上的正則語言，則~L=T*—L也是
13. 若L是正則語言，則L的反轉(zhuǎn)也是
14. 若L是字母表T上的正則語言，h是T上的一個同態(tài)，則h(L)也是正則的
15. 若h是字母表A到字母表T的同態(tài)，且L是T上的正則語言，則逆同態(tài)h^-1(L)也是正則的
posted @
2023-09-09 08:11 春秋十二月 閱讀(1129) |
評論 (0) |
編輯 收藏1. 空性：對于R，若給定形式是自動機比如£-NFA，則等價于判定能否從初始狀態(tài)到達接受狀態(tài)，這需計算可達狀態(tài)集合，若任一接受狀態(tài)在里面，則為非空，否則為空。耗時不超過O(n^2)，n為自動機的狀態(tài)數(shù)。若給定形式是正則表達式，則可先轉(zhuǎn)為£-NFA，再計算可達狀態(tài)集合，如此增多轉(zhuǎn)化時間O(s)，s為正則表達式的長度。也可不轉(zhuǎn)為自動機，直接根據(jù)基礎(chǔ)歸納規(guī)則用遞推法判定，耗時為O(s)。 對于CFL，等價于判定開始符號是否為產(chǎn)生的，若是則非空，否則為空。如直接用產(chǎn)生變元的基礎(chǔ)歸納法計算，那耗時O(n^2)，n為文法G的規(guī)模，接近變元的個數(shù)。一個改進的算法實現(xiàn)，預(yù)先建立以變元為索引的數(shù)組、每個變元的鏈接（產(chǎn)生式內(nèi)鏈接、產(chǎn)生式間鏈接），則耗時O(n)
2. 成員性：設(shè)串w的長度為n。對于R，等價于判定自動機能否接受w，若給定形式是DFA，則耗時O(n)。若給定形式是NFA，則耗時O(n*s^2)，s為狀態(tài)數(shù)，如NFA有£轉(zhuǎn)移，那需先計算它的閉包，耗時增多O(s^2)，可見總耗時還是O(n*s^2)。若給定形式是正則表達式，則先轉(zhuǎn)為NFA，耗時增多O(r)，r為表達式的長度。 對于CFL，等價于判定從文法G的開始符號S能否推導(dǎo)出w，一般用CYK算法構(gòu)造產(chǎn)生式三角表，再查看S是否屬于表的頂點集合，若屬于則能推導(dǎo)出w，否則不能，耗時為O(n^3)
posted @
2023-09-09 08:09 春秋十二月 閱讀(88) |
評論 (0) |
編輯 收藏因為一個整數(shù)p，若檢測為合數(shù)，這永遠是真命題；而檢測為素數(shù)，這命題只以較大概率成立。 可構(gòu)造一種NP檢測算法，步驟如下：
1. 猜測p（位長度n）的因子列表｛p1,p2,…pi｝，這是非確定的，每個分支耗時O(n)
2. 驗證p1*p2*…pi？=p-1，耗時不超過O(n^2)
3. 若各因子乘積等于p-1，則用當前算法遞歸驗證每個因子都是素數(shù)
4. 隨機選擇p最小剩余系內(nèi)的一個數(shù)x，計算x^((p-1)/q) （q遍歷上述列表經(jīng)過步驟3驗證過的素因子）是否都不同余于1模p，若是則必有x^(p-1)同余于1模p，則由指數(shù)整除p的歐拉數(shù)及費馬小定理，知p為素數(shù)，考慮到有少量的合數(shù)也滿足費馬小定理，故需多次選擇x重復(fù)驗證，選擇個數(shù)最多為log(p)
分析：本算法涉及的數(shù)論定理——設(shè)p是奇素數(shù)，p-1的所有素因子是q1,q2,…qs，那么g為原根的充要條件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
結(jié)論：第3步可以看成遞歸調(diào)用樹，每個頂點為待檢測整數(shù)，其每個子結(jié)點為一個因子，則最多n層，每層至多耗時O(n^4)，所以每個路徑即檢測p是否素數(shù)的非確定任一分支中，總耗時O(n^5)。 2002年，印度科學(xué)家發(fā)現(xiàn)素檢測確定性多項式時間算法，于是從NP前進到了P
posted @
2023-09-09 08:07 春秋十二月 閱讀(685) |
評論 (0) |
編輯 收藏為什么命題邏輯有效性是可判定的，而謂詞邏輯有效性是不可判定的？
因為命題邏輯由有限個合式公式及原子命題構(gòu)成，且原子命題的取值只有真、假兩種，簡單的判定方法是真值表窮舉，其復(fù)雜度為指數(shù)級：2^N，N為原子命題數(shù)量。快速的方法是先轉(zhuǎn)成合取范式（輸入是由否定、而且、或者、蘊含四種連接詞構(gòu)成的語法正確的命題邏輯公式，經(jīng)過對公式結(jié)構(gòu)歸納作蘊含釋放、否定原子、分配律變換三步處理，同時運用DAG優(yōu)化：共享終止即葉子結(jié)點、刪除冗余的測試結(jié)點、刪除重復(fù)的有相同子圖結(jié)構(gòu)的內(nèi)部結(jié)點，輸出等價最小的合取范式），再檢測合取范式的有效性（檢查所有子句，若每個子句包含至少一個原子及其否定形式，則有效，否則因為存在一種真值指派使其為假而導(dǎo)致整個合取范式無效），其復(fù)雜度為多項式級：N*logN+N，N為公式長度。謂詞邏輯基于命題邏輯擴展，添加了變元、函數(shù)、量詞“所有”與“存在”，如果量詞沒有約束變元范圍即定義域無限，那么函數(shù)值域也是無限的，另外可能引入的自由變元不受限制，這導(dǎo)致了解空間是無限的，所以不存在通用算法去判定任意謂詞邏輯公式是否有效，具體證明可以用pcp歸約，即構(gòu)造一組特定的謂詞邏輯公式，它是有效的當且僅當pcp實例有解，又已知pcp是不可判定的，故該特定謂詞邏輯有效性是不可判定的，由于任意包括特定，所以謂詞邏輯有效性是不可判定的
posted @
2023-09-09 08:05 春秋十二月 閱讀(83) |
評論 (0) |
編輯 收藏