2009年1月5日 星期一

網頁密碼 - ASCII 的因式分解

先看看以下一段 Code
function check(){
pw = document.getElementById('password').value.toLowerCase();
pc = 1;
for(i = 0; i < pw.length; i++){
pc *= password.charCodeAt(i);
}
if(pc==20356804851768000){
window.location=pw+".htm";
}
else{
alert("Wrong Password.");
}
}

由於腳本中的 "toLowerCase", 所以所有大楷字母均可撇除。由於密碼 pw 是檔案名稱的一部份,所以 \ / : * ? " < > | 均不可使用。
我們假設該密碼是由小楷字母、數字和檔名可用的普通符號組成。
普通符號ASCII範圍:32-47, 58-64, 91-96, 123-126
剔除檔名不可用符號後的範圍:32-33, 35-41, 43-46, 59, 61, 64, 91, 93-96, 123, 125-126
數字ASCII範圍:48-57
大楷字母ASCII範圍:65-90
小楷字母ASCII範圍:97-122
一般來說,ASCII 為 32-126 的字元是此類密碼的輸入範圍。


討論
1. 是否存在唯一密碼?
答:當密碼長度大於一,存在不同字元時,便不存在唯一密碼。因為若密碼是 "ab",輸入 "ba" 亦能通過驗證。

2. 若忽略字元的位置 (如ab ,ba 均可作為密碼),是否仍存在唯一密碼?
答:不存在。因為一個數可以有多種組合:例如密碼鍵是 1073741824,6個空格(32)和5個@(64)均可得出 1073741824。

3. 若給定一個長度,是否仍存在唯一密碼?
答:仍然不存在。對於 a,b,c,d 於 [32,126] , 以下是 a*b = c*d 的組合:
abeqcd.txt


解密
1. 評估密碼長度
利用對數換底公式即可得出大約長度。 例如假設密碼字元的 ASCII 碼均在 [32,126],密碼鍵為 20356804851768000,
計算 log 20356804851768000 / log 126 及 log 20356804851768000 / log 32
得出 7.765 至 10.835 ,下界上捨入、上界下捨入,得出 8 至 10 字元。

2. 因式分解
利用電腦計算程式如 Maxima ,可快速因式分解此類密碼鍵。 (若因數包含大質數則例外,但 [32,126] 是十分小,所以速度仍然很快。)
(%i1) factor(20356804851768000);
(%o1) 2^6*3^2*5^3*7*11*19*23*29^2*97*103

結果往往是出人意表的,因為有時結果中包含一些相對大的質數,便可立即得出其中包含的字元。
在此例子中,97 和 103 (a 和 g) 出現了。

3. 組合因數
剩下的 2^6*3^2*5^3*7*11*19*23*29^2 共有 17 項,要如何合併至剩下 6 至 8 項?
密碼範圍內可用的因式:
32,33,35,36,38,40,44,45,46,48,49,50,54,55,56,57,64,95,96,98,99,100,105,108,110,112,114,115,116,120,121,125,126 (共 34 個)
利用暴力破解,共有 35C8 = 23525820 個組合
符合的數
1*1*95*110*115*116*116*126
1*1*105*110*114*115*116*116
1*33*35*46*50*57*116*116
1*35*38*45*46*55*116*116

_nstt~
inrstt
!#.29tt
#&-.7tt
加上之前的 a 和 g ,得
_agnstt~
aginrstt
!#.29agtt
#&-.7agtt

4. 白撞
利用 anagram 軟件查詢第二個 (全部字母):
http://wordsmith.org/anagram/anagram.cgi?anagram=aginrstt
得出密碼為 starting 。


應用
如剛才例子,有4個不同字元組合均可解得上述密碼,再加上本身字元的排序,其組合亦十分多。
若果想建立唯一的密碼,便需要加上密碼長度和密碼字元排序的資訊。

若假設只包含小楷字母,上述例子的可用密碼因式只剩下:
98,99,100,105,108,110,112,114,115,116,120,121 (共 12 項)
那麼暴力破解的組合只需 13C8 = 1287

一般來說,網頁密碼很小會包含符號,所以在假設時,可先考慮英數字符。

3 則留言:

  1. 作者已經移除這則留言。

    回覆刪除
  2. 作者已經移除這則留言。

    回覆刪除
  3. _[]={0,32,33,35,36,38,40,44,45,46,48,49,50,54,55,56,
    57,64,95,96,97,98,99,100,103,105,108,110,112,114,115,
    116,120,121,125,126};char __[20]={0};p(__int64 ___,int
    ____,int _____){while(__[____]=_[--_____])___==__[____]
    ?printf("%s\n", __):(___%__[____]==0?p(___/__[____],____
    +1,_____+1):0);};main(){p(20356804851768000,0,36);}

    回覆刪除