1.å¦ä½å好pythonèªå¨åè¿ç»´
2.å¦ä½å®å
¨å°åå¨å¯ç
3.å¦ä½å©ç¨python使ç¨libsvm
å¦ä½å好pythonèªå¨åè¿ç»´
éç移å¨äºèç½çæ®åï¼æå¡å¨è¿ç»´æé¢ä¸´çææä¹éä¹è¶æ¥è¶å¤§ãå½è§æ¨¡å¢é¿å°ä¸å®ç¨åº¦ï¼æå¨ç®¡çæ¹å¼å·²ç»æ æ³åºå¯¹ï¼èªå¨åè¿ç»´æ为解å³é®é¢çé¶å¼¹ãPythonååå ¶çµæ´»æ§ï¼å¨èªå¨åè¿ç»´æ¹é¢å·²ç»è¢«å¹¿æ³ä½¿ç¨ï¼è½å¤å¤§å¤§æé«è¿ç»´æçï¼æå¡å¨é群çè§æ¨¡è¶å¤§ï¼ä¼å¿è¶ææ¾ãç°å¨ä¸è®ºæ¯Linuxè¿ç»´å·¥ç¨å¸è¿æ¯Unixè¿ç»´å·¥ç¨å¸é½éè¦ææ¡Pythonï¼ä»¥æé«è¿ç»´æçã第ä¸ä¸ªé¶æ®µï¼å级ï¼ææ¡Pythonçè¯æ³åä¸äºå¸¸ç¨åºç使ç¨
ææ¡ä¸é¨è¯è¨æ好çæ¹æ³å°±æ¯ç¨å®ï¼æ以æè§å¾è¾¹å¦è¯æ³è¾¹å·Leetcodeæ¯ææ¡Pythonæå¿«çæ¹å¼ä¹ä¸ã
å¾å¤åªéè¦å°Pythonä½ä¸ºèæ¬æè å°±æ¯åä¸äºå°ç¨åºå¤çå¤çææ¬çè¯ï¼å°è¿ä¸ä¸ªé¶æ®µå°±è¶³å¤äºï¼è¿ä¸ªé¶æ®µå·²ç»å¯ä»¥å¸®æ们å®æå¾å¤å¾å¤çäºæ äºãä½æ¯å¦ææ¯ä¸ä¸ªä¸ä¸å¦ä¹ Pythonçï¼ææè¿éè¦åªåçå级ï¼é¦å ï¼å½å ç大å¤æ°äººé½æ¯å¦ä¹ äºå ¶ä»è¯è¨ï¼Cï¼C++,–源码成都源码时代助教Javaçï¼ä¹åæ¥å¦ä¹ Pythonçï¼æ以Pythonåè¿äºè¯è¨çä¸åï¼ä¹å°±æ¯pythonicçä¸è¥¿éè¦ä¸äºæ¶é´å»å¦ä¹ äºè§£åææ¡ï¼å¦å¤ï¼å¯¹äºèªå·±é¢åçé¢åçåºææ¶çææ¡ä¹éè¦å¾é¿çæ¶é´å»ææ¡ï¼æåï¼å¦ææ³ç¬ç«å®æä¸ä¸ªPythonç项ç®ï¼é¡¹ç®çå¸å±ï¼åå¸ï¼å¼æºçé½æ¯éè¦èèçé®é¢ã
第äºä¸ªé¶æ®µï¼ä¸çº§ï¼ææ¡èªå·±ç¹å®é¢åçåºï¼ææ¡pythonicåæ³ï¼é常çæPythonçç¹æ§
æ¨èç第ä¸æ¬ä¹¦æ¯ãç¼åé«è´¨é代ç âæ¹åpythonç¨åºç个建议ãï¼è¿æ¬ä¹¦å¤§æ¦çæäºä¸Pythonå·¥ç¨çæ件å¸å±ï¼æ´å¤çæ»ç»äºå¦ä½ååºpythonicç代ç ï¼å¦å¤ï¼ä¹ä»ç»äºä¸äºå¸¸ç¨çåºã
è¿éé¦å æ¨èå¨è ¾è®¯å®æ¹è¯¾ç¨æ¸ éä¸è¿è¡ç´æå¦ä¹ ï¼æå·å°±è½æ å¿ä¸ç´å¦ï¼æ¯å¤©æä¸é½æ¯é«æ¸ ç´æ(ä¼é¹ ççï¼ä¸é´æ¯æåå ä¸è¿ä¸ªè¿å¨ä¸èµ·å°±è½å¤äºï¼ï¼é¤æ¤ä¹å¤åºäºpython2.7å¨ç½ä¸ç书ç±éåäºé头å¼å§ä¸ç´è¯»å®ï¼ä½ä¸ºä¸ä¸ªå¼å人åï¼é¤äºåºæ¬çè¯æ³ï¼è¿æ¬ä¹¦éé¢æå°äºä¸äºå ¶ä»ç常ç¨çåºï¼çäºå»èå¸åçå¾å¤ä¸è¥¿ï¼æè§ä»çæè·¯ï¼ä»¥ååå客å书çé«åº¦ï¼æ¦æ¬æ§ï¼åçæ§é½åå好ï¼è¿æ¬ä¹¦è¯»å®ä¹åï¼ç¸ä¿¡å°±è½å¤å¨æåå¾å¤ä¸è¥¿äºï¼è½å¤å°½æ çç©è½¬Python解说å¨äºã
è¦æ³æ·±å ¥çäºè§£Pythonï¼æçæ¶åççPythonçæºç ä¹æ¯å¾éè¦çï¼èªå·±éè¿è¯»ææºç ï¼æ¥å½»åºçäºè§£Pythonçæ ¸å¿æºå¶ï¼è¿éæ¨èãPythonæºç åæââ深度æ¢ç´¢å¨æè¯è¨æ ¸å¿ææ¯ãï¼è¿æ¬ä¹¦å¹¶æ²¡æçå®ï¼åªæ¯å¨éè¦æ·±å ¥äºè§£Pythonæ个åè½æè æ°æ®ç»æçæ¶åççç¸å ³ç« èï¼ä¹è§å¾åçåªæµ ã
èªå·±é¢åç书ç±åèµæä¹è¯å®å¾å¤ï¼æ¯å¦webå¼åçææ¶é½æå¾å¤ï¼åªæäºè§£çæäºææææ¶ï¼å¨éæ©çæ¶åæè½è¡¡éå©å¼ï¼ç¶åæ·±å ¥ææ¡æäºææ¶ã
å¦ä½å®å ¨å°åå¨å¯ç
ãä¿æ¤å¯ç æ好ççæ¹å¼å°±æ¯ä½¿ç¨å¸¦ççå¯ç hash(salted password hashing).对å¯ç è¿è¡hashæä½æ¯ä¸ä»¶å¾ç®åçäºæ ï¼ä½æ¯å¾å¤äººé½ç¯äºéãæ¥ä¸æ¥æå¸æå¯ä»¥è¯¦ç»çéè¿°å¦ä½æ°å½ç对å¯ç è¿è¡hashï¼ä»¥å为ä»ä¹è¦è¿æ ·åã
ããéè¦æé
ããå¦æä½ æç®èªå·±åä¸æ®µä»£ç æ¥è¿è¡å¯ç hashï¼é£ä¹èµ¶ç´§åä¸å§ãè¿æ ·å¤ªå®¹æç¯éäºãè¿ä¸ªæééç¨äºæ¯ä¸ä¸ªäººï¼ä¸è¦èªå·±åå¯ç çhashç®æ³ ï¼å ³äºä¿åå¯ç çé®é¢å·²ç»æäºæççæ¹æ¡ï¼é£å°±æ¯ä½¿ç¨phpassæè æ¬ææä¾çæºç ã
ããä»ä¹æ¯hash
ããhash("hello") = 2cfdba5fb0aeeb2ac5b9ee1be5c1faeb
hash("hbllo") = ccdfacfad6affaafe7ddf
hash("waltz") = c0efcbc6bd9ecfbfda8ef
ããHashç®æ³æ¯ä¸ç§ååçå½æ°ãå®å¯ä»¥æä»»ææ°éçæ°æ®è½¬æ¢æåºå®é¿åº¦çâæ纹âï¼è¿ä¸ªè¿ç¨æ¯ä¸å¯éçãèä¸åªè¦è¾å ¥åçæ¹åï¼åªæåªæä¸ä¸ªbitï¼è¾åºçhashå¼ä¹ä¼æå¾å¤§ä¸åãè¿ç§ç¹æ§æ°å¥½åéç¨æ¥ç¨æ¥ä¿åå¯ç ãå 为æ们å¸æ使ç¨ä¸ç§ä¸å¯éçç®æ³æ¥å å¯ä¿åçå¯ç ï¼åæ¶åéè¦å¨ç¨æ·ç»éçæ¶åéªè¯å¯ç æ¯å¦æ£ç¡®ã
ããå¨ä¸ä¸ªä½¿ç¨hashçè´¦å·ç³»ç»ä¸ï¼ç¨æ·æ³¨åå认è¯ç大è´æµç¨å¦ä¸ï¼
ãã1, ç¨æ·å建èªå·±çè´¦å·
2, ç¨æ·å¯ç ç»è¿hashæä½ä¹ååå¨å¨æ°æ®åºä¸ã没æä»»ä½ææçå¯ç åå¨å¨æå¡å¨ç硬çä¸ã
3, ç¨æ·ç»éçæ¶åï¼å°ç¨æ·è¾å ¥çå¯ç è¿è¡hashæä½åä¸æ°æ®åºéä¿åçå¯ç hashå¼è¿è¡å¯¹æ¯ã
4, å¦æhashå¼å®å ¨ä¸æ ·ï¼å认为ç¨æ·è¾å ¥çå¯ç æ¯æ£ç¡®çãå¦å就认为ç¨æ·è¾å ¥äºæ æçå¯ç ã
5, æ¯æ¬¡ç¨æ·å°è¯ç»éçæ¶åå°±éå¤æ¥éª¤3åæ¥éª¤4ã
ããå¨æ¥éª¤4çæ¶åä¸è¦åè¯ç¨æ·æ¯è´¦å·è¿æ¯å¯ç éäºãåªéè¦æ¾ç¤ºä¸ä¸ªéç¨çæ示ï¼æ¯å¦è´¦å·æå¯ç ä¸æ£ç¡®å°±å¯ä»¥äºãè¿æ ·å¯ä»¥é²æ¢æ»å»è æ举ææçç¨æ·åã
ããè¿éè¦æ³¨æçæ¯ç¨æ¥ä¿æ¤å¯ç çhashå½æ°è·æ°æ®ç»æ课ä¸è§è¿çhashå½æ°ä¸å®å ¨ä¸æ ·ãæ¯å¦å®ç°hash表çhashå½æ°è®¾è®¡çç®çæ¯å¿«éï¼ä½æ¯ä¸å¤å®å ¨ãåªæå å¯hashå½æ°(cryptographic hash functions)å¯ä»¥ç¨æ¥è¿è¡å¯ç çhashãè¿æ ·çå½æ°æSHA, SHA, RipeMD, WHIRLPOOLçã
ããä¸ä¸ªå¸¸è§çè§å¿µå°±æ¯å¯ç ç»è¿hashä¹ååå¨å°±å®å ¨äºãè¿æ¾ç¶æ¯ä¸æ£ç¡®çãæå¾å¤æ¹å¼å¯ä»¥å¿«éçä»hashæ¢å¤ææçå¯ç ãè¿è®°å¾é£äºmd5ç ´è§£ç½ç«å§ï¼åªéè¦æ交ä¸ä¸ªhashï¼ä¸å°ä¸ç§éå°±è½ç¥éç»æãæ¾ç¶ï¼å纯ç对å¯ç è¿è¡hashè¿æ¯è¿è¿è¾¾ä¸å°æ们çå®å ¨éæ±ãä¸ä¸é¨åå 讨论ä¸ä¸ç ´è§£å¯ç hashï¼è·åææ常è§çæ段ã
ããå¦ä½ç ´è§£hash
ããåå ¸åæ´åç ´è§£æ»å»(Dictionary and Brute Force Attacks)
ããæ常è§çç ´è§£hashæ段就æ¯çæµå¯ç ãç¶å对æ¯ä¸ä¸ªå¯è½çå¯ç è¿è¡hashï¼å¯¹æ¯éè¦ç ´è§£çhashåçæµçå¯ç hashå¼ï¼å¦æ两个å¼ä¸æ ·ï¼é£ä¹ä¹åçæµçå¯ç å°±æ¯æ£ç¡®çå¯ç ææãçæµå¯ç æ»å»å¸¸ç¨çæ¹å¼å°±æ¯åå ¸æ»å»åæ´åæ»å»ã
ããDictionary Attack
Trying apple : failed
Trying blueberry : failed
Trying justinbeiber : failed
...
Trying letmein : failed
Trying s3cr3t : success!
ããåå ¸æ»å»æ¯å°å¸¸ç¨çå¯ç ï¼åè¯ï¼çè¯åå ¶ä»å¯è½ç¨æ¥åå¯ç çå符串æ¾å°ä¸ä¸ªæ件ä¸ï¼ç¶å对æ件ä¸çæ¯ä¸ä¸ªè¯è¿è¡hashï¼å°è¿äºhashä¸éè¦ç ´è§£çå¯ç hashæ¯è¾ãè¿ç§æ¹å¼çæåçåå³äºå¯ç åå ¸ç大å°ä»¥ååå ¸çæ¯å¦åéã
ããBrute Force Attack
Trying aaaa : failed
Trying aaab : failed
Trying aaac : failed
...
Trying acdb : failed
Trying acdc : success!
ããæ´åæ»å»å°±æ¯å¯¹äºç»å®çå¯ç é¿åº¦ï¼å°è¯æ¯ä¸ç§å¯è½çå符ç»åãè¿ç§æ¹å¼éè¦è±è´¹å¤§éç计ç®æºæ¶é´ãä½æ¯ç论ä¸åªè¦æ¶é´è¶³å¤ï¼æåå¯ç ä¸å®è½å¤ç ´è§£åºæ¥ãåªæ¯å¦æå¯ç 太é¿ï¼ç ´è§£è±è´¹çæ¶é´å°±ä¼å¤§å°æ æ³æ¿åã
ããç®å没ææ¹å¼å¯ä»¥é»æ¢åå ¸æ»å»åæ´åæ»å»ãåªè½æ³åæ³è®©å®ä»¬åçä½æãå¦æä½ çå¯ç hashç³»ç»è®¾è®¡çæ¯å®å ¨çï¼é£ä¹ç ´è§£hashå¯ä¸çæ¹å¼å°±æ¯è¿è¡åå ¸æè æ´åæ»å»äºã
ããæ¥è¡¨ç ´è§£(Lookup Tables)
ãã对äºç¹å®çhashç±»åï¼å¦æéè¦ç ´è§£å¤§éhashçè¯ï¼æ¥è¡¨æ¯ä¸ç§é常ææèä¸å¿«éçæ¹å¼ãå®çç念就æ¯é¢å 计ç®(pre-compute)åºå¯ç åå ¸ä¸æ¯ä¸ä¸ªå¯ç çhashãç¶åæhashå对åºçå¯ç ä¿åå¨ä¸ä¸ªè¡¨éãä¸ä¸ªè®¾è®¡è¯å¥½çæ¥è¯¢è¡¨ç»æï¼å³ä½¿åå¨äºæ°å亿个hashï¼æ¯ç§éä»ç¶å¯ä»¥æ¥è¯¢æç¾ä¸å个hashã
ããå¦æä½ æ³æåä¸æ¥è¡¨ç ´è§£hashçè¯å¯ä»¥å°è¯ä¸ä¸å¨CraskStationä¸ç ´è§£ä¸ä¸é¢çsha hashã
ããcb4b0aafcddfee9fbb8bcf3a7f0dbaadfc
eacbadcdc7d8fbeb7c7bd3a2cbdbfcbbbae7
e4ba5cbdce6cd1cfa3bd8dabcb3ef9f
b8b8acfcbcac7bfba9fefeebbdcbd
ããååæ¥è¡¨ç ´è§£(Reverse Lookup Tables)
ããSearching for hash(apple) in users' hash list... : Matches [alice3, 0bob0, charles8]
Searching for hash(blueberry) in users' hash list... : Matches [usr, timmy, john]
Searching for hash(letmein) in users' hash list... : Matches [wilson, dragonslayerX, joe]
Searching for hash(s3cr3t) in users' hash list... : Matches [bruce, knuth, john]
Searching for hash(z@hjja) in users' hash list... : No users used this password
ããè¿ç§æ¹å¼å¯ä»¥è®©æ»å»è ä¸é¢å 计ç®ä¸ä¸ªæ¥è¯¢è¡¨çæ åµä¸åæ¶å¯¹å¤§éhashè¿è¡åå ¸åæ´åç ´è§£æ»å»ã
ããé¦å ï¼æ»å»è ä¼æ ¹æ®è·åå°çæ°æ®åºæ°æ®å¶ä½ä¸ä¸ªç¨æ·åå对åºçhash表ãç¶åå°å¸¸è§çåå ¸å¯ç è¿è¡hashä¹åï¼è·è¿ä¸ªè¡¨çhashè¿è¡å¯¹æ¯ï¼å°±å¯ä»¥ç¥éç¨åªäºç¨æ·ä½¿ç¨äºè¿ä¸ªå¯ç ãè¿ç§æ»å»æ¹å¼å¾æææï¼å 为é常æ åµä¸å¾å¤ç¨æ·é½ä¼æ使ç¨ç¸åçå¯ç ã
ãã彩è¹è¡¨ (Rainbow Tables)
ãã彩è¹è¡¨æ¯ä¸ç§ä½¿ç¨ç©ºé´æ¢åæ¶é´çææ¯ãè·æ¥è¡¨ç ´è§£å¾ç¸ä¼¼ãåªæ¯å®çºç²äºä¸äºç ´è§£æ¶é´æ¥è¾¾å°æ´å°çåå¨ç©ºé´çç®çãå 为彩è¹è¡¨ä½¿ç¨çåå¨ç©ºé´æ´å°ï¼æ以åä½ç©ºé´å°±å¯ä»¥åå¨æ´å¤çhashã彩è¹è¡¨å·²ç»è½å¤ç ´è§£8ä½é¿åº¦çä»»æmd5hashã彩è¹è¡¨å ·ä½çåçå¯ä»¥åè/
ããä¸ä¸ç« èæ们ä¼è®¨è®ºä¸ç§å«åâçâ(salting)çææ¯ãéè¿è¿ç§ææ¯å¯ä»¥è®©æ¥è¡¨å彩è¹è¡¨çæ¹å¼æ æ³ç ´è§£hashã
ããå ç(Adding Salt)
ããhash("hello") = 2cfdba5fb0aeeb2ac5b9ee1be5c1faeb
hash("hello" + "QxLUF1bgIAdeQX") = 9ecfaebfe5ed3bacffed1
hash("hello" + "bv5PehSMfVCd") = d1d3ec2e6ffddedab8eac9eaaefab
hash("hello" + "YYLmfY6IehjZMQ") = ac3cb9eb9cfaffdc8aedb2c4adf1bf
ããæ¥è¡¨å彩è¹è¡¨çæ¹å¼ä¹æ以æææ¯å 为æ¯ä¸ä¸ªå¯ç çé½æ¯éè¿åæ ·çæ¹å¼æ¥è¿è¡hashçãå¦æ两个ç¨æ·ä½¿ç¨äºåæ ·çå¯ç ï¼é£ä¹ä¸å®ä»ä»¬çå¯ç hashä¹ä¸å®ç¸åãæ们å¯ä»¥éè¿è®©æ¯ä¸ä¸ªhashéæºåï¼åä¸ä¸ªå¯ç hash两次ï¼å¾å°çä¸åçhashæ¥é¿å è¿ç§æ»å»ã
ããå ·ä½çæä½å°±æ¯ç»å¯ç å ä¸ä¸ªéå³çåç¼æè åç¼ï¼ç¶ååè¿è¡hashãè¿ä¸ªéå³çåç¼æè åç¼æ为âçâãæ£å¦ä¸é¢ç»åºçä¾åä¸æ ·ï¼éè¿å çï¼ç¸åçå¯ç æ¯æ¬¡hashé½æ¯å®å ¨ä¸ä¸æ ·çå符串äºãæ£æ¥ç¨æ·è¾å ¥çå¯ç æ¯å¦æ£ç¡®çæ¶åï¼æ们ä¹è¿éè¦è¿ä¸ªçï¼æ以çä¸è¬é½æ¯è·hashä¸èµ·ä¿åå¨æ°æ®åºéï¼æè ä½ä¸ºhashå符串çä¸é¨åã
ããçä¸éè¦ä¿å¯ï¼åªè¦çæ¯éæºçè¯ï¼æ¥è¡¨ï¼å½©è¹è¡¨é½ä¼å¤±æãå 为æ»å»è æ æ³äºå ç¥éçæ¯ä»ä¹ï¼ä¹å°±æ²¡æåæ³é¢å 计ç®åºæ¥è¯¢è¡¨å彩è¹è¡¨ãå¦ææ¯ä¸ªç¨æ·é½æ¯ä½¿ç¨äºä¸åççï¼é£ä¹ååæ¥è¡¨æ»å»ä¹æ²¡æ³æåã
ããä¸ä¸èï¼æ们ä¼ä»ç»ä¸äºçç常è§çé误å®ç°ã
ããé误çæ¹å¼ï¼çççåççå¤ç¨
ããæ常è§çé误å®ç°å°±æ¯ä¸ä¸ªçå¨å¤ä¸ªhashä¸ä½¿ç¨æè 使ç¨ççå¾çã
ããççå¤ç¨(Salt Reuse)
ããä¸ç®¡æ¯å°ç硬ç¼ç å¨ç¨åºéè¿æ¯éæºä¸æ¬¡çæçï¼å¨æ¯ä¸ä¸ªå¯ç hashé使ç¨ç¸åççä¼ä½¿è¿ç§é²å¾¡æ¹æ³å¤±æãå 为ç¸åçå¯ç hash两次å¾å°çç»æè¿æ¯ç¸åçãæ»å»è å°±å¯ä»¥ä½¿ç¨ååæ¥è¡¨çæ¹å¼è¿è¡åå ¸åæ´åæ»å»ãåªè¦å¨å¯¹åå ¸ä¸æ¯ä¸ä¸ªå¯ç è¿è¡hashä¹åå ä¸è¿ä¸ªåºå®ççå°±å¯ä»¥äºãå¦ææ¯æµè¡çç¨åºç使ç¨äºç¡¬ç¼ç ççï¼é£ä¹ä¹å¯è½åºç°é对è¿ç§ç¨åºçè¿ä¸ªççæ¥è¯¢è¡¨å彩è¹è¡¨ï¼ä»èå®ç°å¿«éç ´è§£hashã
ããç¨æ·æ¯æ¬¡å建æè ä¿®æ¹å¯ç ä¸å®è¦ä½¿ç¨ä¸ä¸ªæ°çéæºçç
ããççç
ããå¦æççä½æ°å¤ªççè¯ï¼æ»å»è ä¹å¯ä»¥é¢å å¶ä½é对ææå¯è½çççæ¥è¯¢è¡¨ãæ¯å¦ï¼3ä½ASCIIå符ççï¼ä¸å ±æxx = ,ç§å¯è½æ§ãçèµ·æ¥å¥½åå¾å¤ãåå¦æ¯ä¸ä¸ªçå¶ä½ä¸ä¸ª1MBçå å«å¸¸è§å¯ç çæ¥è¯¢è¡¨ï¼,个çææ¯GBãç°å¨ä¹°ä¸ª1TBç硬çé½åªè¦å ç¾åèå·²ã
ããåºäºåæ ·ççç±ï¼åä¸ä¸è¦ç¨ç¨æ·åå为çãè½ç¶å¯¹äºæ¯ä¸ä¸ªç¨æ·æ¥è¯´ç¨æ·åå¯è½æ¯ä¸åçï¼ä½æ¯ç¨æ·åæ¯å¯é¢æµçï¼å¹¶ä¸æ¯å®å ¨éæºçãæ»å»è å®å ¨å¯ä»¥ç¨å¸¸è§çç¨æ·åä½ä¸ºçæ¥å¶ä½æ¥è¯¢è¡¨å彩è¹è¡¨ç ´è§£hashã
ããæ ¹æ®ä¸äºç»éªå¾åºæ¥çè§åå°±æ¯çç大å°è¦è·hashå½æ°çè¾åºä¸è´ãæ¯å¦ï¼SHAçè¾åºæ¯bits(bytes),ççé¿åº¦ä¹åºè¯¥æ¯ä¸ªåèçéæºæ°æ®ã
ããé误çæ¹å¼ï¼åéhashåå¤æªçhashå½æ°
ããè¿ä¸è讨论å¦å¤ä¸ä¸ªå¸¸è§çhashå¯ç ç误解:å¤æªçhashç®æ³ç»åã人们å¯è½è§£å³çå°ä¸åçhashå½æ°ç»åå¨ä¸èµ·ç¨å¯ä»¥è®©æ°æ®æ´å®å ¨ãä½å®é ä¸ï¼è¿ç§æ¹å¼å¸¦æ¥çææå¾å¾®å°ãåèå¯è½å¸¦æ¥ä¸äºäºéæ§çé®é¢ï¼çè³ææ¶åä¼è®©hashæ´å çä¸å®å ¨ãæ¬æä¸å¼å§å°±æå°è¿ï¼æ°¸è¿ä¸è¦å°è¯èªå·±åhashç®æ³ï¼è¦ä½¿ç¨ä¸å®¶ä»¬è®¾è®¡çæ åç®æ³ãæäºäººä¼è§å¾éè¿ä½¿ç¨å¤ä¸ªhashå½æ°å¯ä»¥éä½è®¡ç®hashçé度ï¼ä»èå¢å ç ´è§£çé¾åº¦ãéè¿åæ ¢hash计ç®é度æ¥é²å¾¡æ»å»ææ´å¥½çæ¹æ³ï¼è¿ä¸ªä¸æä¼è¯¦ç»ä»ç»ã
ããä¸é¢æ¯ä¸äºç½ä¸æ¾å°çå¤æªçhashå½æ°ç»åçæ ·ä¾ã
ããmd5(sha1(password))
md5(md5(salt) + md5(password))
sha1(sha1(password))
sha1(str_rot(password + salt))
md5(sha1(md5(md5(password) + sha1(password)) + md5(password)))
ããä¸è¦ä½¿ç¨ä»ä»¬ï¼
ãã注æï¼è¿é¨åçå å®¹å ¶å®æ¯åå¨äºè®®çï¼ææ¶å°è¿å¤§éé®ä»¶è¯´ç»åhashå½æ°æ¯ææä¹çãå 为å¦ææ»å»è ä¸ç¥éæ们ç¨äºåªä¸ªå½æ°ï¼å°±ä¸å¯è½äºå 计ç®åºå½©è¹è¡¨ï¼å¹¶ä¸ç»åhashå½æ°éè¦æ´å¤ç计ç®æ¶é´ã
ããæ»å»è å¦æä¸ç¥éhashç®æ³çè¯èªç¶æ¯æ æ³ç ´è§£hashçãä½æ¯èèå°Kerckhoffsâs principle,æ»å»è é常é½æ¯è½å¤æ¥è§¦å°æºç ç(å°¤å ¶æ¯å 费软件åå¼æºè½¯ä»¶)ãéè¿ä¸äºç®æ ç³»ç»çå¯ç âhash对åºå ³ç³»æ¥éååºç®æ³ä¹ä¸æ¯é常å°é¾ã
ããå¦æä½ æ³ä½¿ç¨ä¸ä¸ªæ åçâå¤æªâçhashå½æ°ï¼æ¯å¦HMACï¼æ¯å¯ä»¥çãä½æ¯å¦æä½ çç®çæ¯æ³åæ ¢hashç计ç®é度ï¼é£ä¹å¯ä»¥è¯»ä¸ä¸åé¢è®¨è®ºçæ ¢éhashå½æ°é¨åãåºäºä¸é¢è®¨è®ºçå ç´ ï¼æ好çåæ³æ¯ä½¿ç¨æ åçç»è¿ä¸¥æ ¼æµè¯çhashç®æ³ã
ããhash碰æ(Hash Collisions)
ããå 为hashå½æ°æ¯å°ä»»ææ°éçæ°æ®æ å°æä¸ä¸ªåºå®é¿åº¦çå符串ï¼æ以ä¸å®åå¨ä¸åçè¾å ¥ç»è¿hashä¹ååæç¸åçå符串çæ åµãå å¯hashå½æ°(Cryptographic hash function)å¨è®¾è®¡çæ¶åå¸æ使è¿ç§ç¢°ææ»å»å®ç°èµ·æ¥ææ¬é¾ä»¥ç½®ä¿¡çé«ãä½æ¶ä¸æ¶çå°±æå¯ç å¦å®¶åç°å¿«éå®ç°hash碰æçæ¹æ³ãæè¿çä¸ä¸ªä¾åå°±æ¯MD5ï¼å®ç碰ææ»å»å·²ç»å®ç°äºã
ãã碰ææ»å»æ¯æ¾å°å¦å¤ä¸ä¸ªè·åå¯ç ä¸ä¸æ ·ï¼ä½æ¯å ·æç¸åhashçå符串ãä½æ¯ï¼å³ä½¿å¨ç¸å¯¹å¼±çhashç®æ³ï¼æ¯å¦MD5,è¦å®ç°ç¢°ææ»å»ä¹éè¦å¤§éçç®å(computing power),æ以å¨å®é 使ç¨ä¸å¶ç¶åºç°hash碰æçæ åµå ä¹ä¸å¤ªå¯è½ãä¸ä¸ªä½¿ç¨å çMD5çå¯ç hashå¨å®é 使ç¨ä¸è·ä½¿ç¨å ¶ä»ç®æ³æ¯å¦SHAä¸æ ·å®å ¨ãä¸è¿å¦æå¯ä»¥çè¯ï¼ä½¿ç¨æ´å®å ¨çhashå½æ°ï¼æ¯å¦SHA, SHA, RipeMD, WHIRLPOOLçæ¯æ´å¥½çéæ©ã
ããæ£ç¡®çæ¹å¼ï¼å¦ä½æ°å½çè¿è¡hash
ããè¿é¨åä¼è¯¦ç»è®¨è®ºå¦ä½æ°å½çè¿è¡å¯ç hashã第ä¸ä¸ªç« èæ¯æåºç¡çï¼è¿ç« èçå 容æ¯å¿ é¡»çãåé¢ä¸ä¸ªç« èæ¯éè¿°å¦ä½ç»§ç»å¢å¼ºå®å ¨æ§ï¼è®©hashç ´è§£åå¾å¼å¸¸å°é¾ã
ããåºç¡ï¼ä½¿ç¨å çhash
ããæ们已ç»ç¥éæ¶æé»å®¢å¯ä»¥éè¿æ¥è¡¨å彩è¹è¡¨çæ¹å¼å¿«éçè·å¾hash对åºçææå¯ç ï¼æ们ä¹ç¥éäºéè¿ä½¿ç¨éæºççå¯ä»¥è§£å³è¿ä¸ªé®é¢ãä½æ¯æ们æä¹çæçï¼æä¹å¨hashçè¿ç¨ä¸ä½¿ç¨çå¢ï¼
ããçè¦ä½¿ç¨å¯ç å¦ä¸å¯é å®å ¨ç伪éæºæ°çæå¨(Cryptographically Secure Pseudo-Random Number Generator (CSPRNG))æ¥äº§çãCSPRNGè·æ®éç伪éæºæ°çæå¨æ¯å¦Cè¯è¨ä¸çrand(),æå¾å¤§ä¸åãæ£å¦å®çåå说æçé£æ ·ï¼CSPRNGæä¾ä¸ä¸ªé«æ åçéæºæ°ï¼æ¯å®å ¨æ æ³é¢æµçãæ们ä¸å¸ææ们ççè½å¤è¢«é¢æµå°ï¼æ以ä¸å®è¦ä½¿ç¨CSPRNGã
å¦ä½å©ç¨python使ç¨libsvm
ä¸ï¼libsvmå ä¸è½½ä¸ä½¿ç¨ï¼
LIBSVMæ¯å°æ¹¾å¤§å¦ææºä»(Lin Chih-Jen)å¯ææçå¼å设计çä¸ä¸ªç®åãæäºä½¿ç¨åå¿«éææçSVM模å¼è¯å«ä¸åå½ç软件å ï¼ä»ä¸ä½æä¾äºç¼è¯å¥½çå¯å¨Windowsç³»åç³»ç»çæ§è¡æ件ï¼è¿æä¾äºæºä»£ç ï¼æ¹ä¾¿æ¹è¿.
æå 解åå¨Cçä¹ä¸ï¼å¦ï¼C:\libsvm-3.
2.
å 为è¦ç¨libsvmèªå¸¦çèæ¬grid.pyåeasy.py,éè¦å»å®ç½ä¸è½½ç»å¾å·¥å ·gnuplot,解åå°cç
3.
è¿å ¥c:\libsvm\toolsç®å½ä¸ï¼ç¨ææ¬ç¼è¾å¨ï¼è®°äºæ¬ï¼edité½å¯ä»¥ï¼ä¿®æ¹grid.pyåeasy.py两个æ件ï¼æ¾å°å ¶ä¸å ³äºgnuplotè·¯å¾çé£é¡¹ï¼æ ¹æ®å®é è·¯å¾è¿è¡ä¿®æ¹ï¼å¹¶ä¿å
4pythonä¸libsvmçè¿æ¥ï¼åèSVMå¦ä¹ ç¬è®°ï¼2ï¼LIBSVMå¨pythonä¸çä½¿ç¨ ï¼
a.æå¼IDLE(python GUI)ï¼è¾å ¥
>>>import sys
>>>sys.version
å¦æä½ çpythonæ¯ä½ï¼å°åºç°å¦ä¸å符ï¼
â2.7.3 (default, Apr , ::) [MSC v. bit (Intel)]â
è¿ä¸ªæ¶åLIBSVMçpythonæ¥å£è®¾ç½®å°é常ç®åãå¨libsvm-3.æ件夹ä¸çwindowsæ件夹ä¸æ¾å°å¨æé¾æ¥åºlibsvm.dllï¼å°å ¶æ·»å å°ç³»ç»ç®å½ï¼å¦`C:\WINDOWS\system\âï¼å³å¯å¨pythonä¸ä½¿ç¨libsvm
b.å¦æä½ æ¯ä½ç请åèæç®ï¼è¯·åèä¸è¿°è¿æ¥ã
5.æ§è¡ä¸ä¸ªå°ä¾å
import os
os.chdir('C:\libsvm-3.\python')#è¯·æ ¹æ®å®é è·¯å¾ä¿®æ¹
from svmutil import
*y, x = svm_read_problem('../heart_scale')#读åèªå¸¦æ°æ®
m = svm_train(y[:], x[:], '-c 4')
p_label, p_acc, p_val = svm_predict(y[:], x[:], m)
##åºç°å¦ä¸ç»æï¼åºè¯¥æ¯æ£ç¡®å®è£ äº
optimization finished, #iter =
nu = 0.
obj = -., rho = 0.
nSV = , nBSV =
Total nSV =
Accuracy = .% (/) (classification)
äºå 个ç®åçä¾å
ä»ä¸è½½å®éªæ°æ®éã并ä¸å°æ°æ®éæ·è´å°C:\libsvm-3.\windowsä¸ï¼å 为ä¹åæ们éè¦å©ç¨è¯¥æ件夹ä¸çå ¶ä»æ件ï¼è¿æ ·æ¯è¾æ¹ä¾¿ï¼å½ç¶ä¹åä½ ç¨ç»å¯¹å°åä¹å¯ä»¥äºï¼
建ç«ä¸ä¸ªpyæ件ï¼åä¸å¦ä¸ä»£ç ï¼
ä¾1ï¼
import os
os.chdir('C:\libsvm-3.\windows')#设å®è·¯å¾
from svmutil import
*y, x = svm_read_problem('train.1.txt')#è¯»å ¥è®ç»æ°æ®
yt, xt = svm_read_problem('test.1.txt')#è®ç»æµè¯æ°æ®
m = svm_train(y, x )#è®ç»
svm_predict(yt,xt,m)#æµè¯
æ§è¡ä¸è¿°ä»£ç ï¼ç²¾åº¦ä¸ºï¼Accuracy = .% (/) (classification)
常ç¨æ¥å£
svm_train() : train an SVM model#è®ç»
svm_predict() : predict testing data#é¢æµ
svm_read_problem() : read the data from a LIBSVM-format file.#读ålibsvmæ ¼å¼çæ°æ®
svm_load_model() : load a LIBSVM model.
svm_save_model() : save model to a file.
evaluations() : evaluate prediction results.
- Function: svm_train#ä¸ç§è®ç»åæ³
There are three ways to call svm_train()
>>> model = svm_train(y, x [, 'training_options'])
>>> model = svm_train(prob [, 'training_options'])
>>> model = svm_train(prob, param)
æå ³åæ°ç设置ï¼read me æ件夹ä¸æ详ç»è¯´æï¼ï¼
Usage: svm-train [options] training_set_file [model_file]
options:
-s svm_type : set type of SVM (default 0)#éæ©åªä¸ç§svm
0 -- C-SVC (multi-class classification)
1 -- nu-SVC (multi-class classification)
2 -- one-class SVM
3 -- epsilon-SVR (regression)
4 -- nu-SVR (regression)
-t kernel_type : set type of kernel function (default 2)#æ¯å¦ç¨kernel trick
0 -- linear: u'*v
1 -- polynomial: (gamma*u'*v + coef0)^degree
2 -- radial basis function: exp(-gamma*|u-v|^2)
3 -- sigmoid: tanh(gamma*u'*v + coef0)
4 -- precomputed kernel (kernel values in training_set_file)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma in kernel function (default 1/num_features)
-r coef0 : set coef0 in kernel function (default 0)
-c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)
-n nu : set the parameter nu of nu-SVC, one-class SVM, and nu-SVR (default 0.5)
-p epsilon : set the epsilon in loss function of epsilon-SVR (default 0.1)
-m cachesize : set cache memory size in MB (default )
-e epsilon : set tolerance of termination criterion (default 0.)
-h shrinking : whether to use the shrinking heuristics, 0 or 1 (default 1)
-b probability_estimates : whether to train a SVC or SVR model for probability estimates, 0 or 1 (default 0)
-wi weight : set the parameter C of class i to weight*C, for C-SVC (default 1)
-v n: n-fold cross validation mode
-q : quiet mode (no outputs)
ä¸æé«é¢æµçåç¡®çï¼
éè¿ä¸å®çè¿ç¨ï¼å¯ä»¥æé«é¢æµçåç¡®ç(å¨æç®2ä¸æ详ç»ä»ç»)ï¼
a.转æ¢æ°æ®ä¸ºlibsvmå¯ç¨å½¢å¼.(å¯ä»¥éè¿ä¸è½½çæ°æ®äºè§£æ ¼å¼ï¼
b.è¿è¡ä¸ä¸ªç®åç尺度åæ¢
c.å©ç¨RBF kernelï¼å©ç¨cross-validationæ¥æ¥æ¾æä½³çåæ° C å r
d.å©ç¨æä½³åæ°C å r ï¼æ¥è®ç»æ´ä¸ªæ°æ®é
e.æµè¯
åçä¾å1ï¼
1.è¿å ¥cmd模å¼ä¸ï¼è¾å ¥å¦ä¸ä»£ç ï¼å°ç°ææ°æ®è¿è¡é度åæ¢ï¼çæåæ¢åçæ°æ®æ件train.1.scale.txt
åæ°è¯´æï¼
-l åæ¢åçä¸é
-u åæ¢åçä¸é
-s åèä¸æ
2æ§è¡ä»¥ä¸ä»£ç
import os
os.chdir('C:\libsvm-3.\windows')#设å®è·¯å¾
from svmutil import
*y, x = svm_read_problem('train.1.scale.txt')#è¯»å ¥è®ç»æ°æ®
yt, xt = svm_read_problem('test.1.scale.txt')#è®ç»æµè¯æ°æ®
m = svm_train(y, x )#è®ç»
svm_predict(yt,xt,m)#æµè¯
精确度为Accuracy = .6% (/) (classification)ã
å¯è§æ们åªæ¯åäºç®åç尺度åæ¢åï¼é¢æµçæ£ç¡®ç大大æåäºã
3éè¿éæ©æä¼åæ°ï¼å次æé«é¢æµçåç¡®çï¼ï¼éè¦ætoolsæ件ä¸çgrid.pyæ·è´å°'C:\libsvm-3.\windows'ä¸ï¼
import os
os.chdir('C:\libsvm-3.\windows')#设å®è·¯å¾
from svmutil import
*from grid import
*rate, param = find_parameters('train.1.scale.txt', '-log2c -3,3,1 -log2g -3,3,1')
y, x = svm_read_problem('train.1.scale.txt')#è¯»å ¥è®ç»æ°æ®
yt, xt = svm_read_problem('test.1.scale.txt')#è®ç»æµè¯æ°æ®
m = svm_train(y, x ,'-c 2 -g 4')#è®ç»
p_label,p_acc,p_vals=svm_predict(yt,xt,m)#æµè¯
æ§è¡ä¸é¢çç¨åºï¼find_parmaterså½æ°ï¼å¯ä»¥æ¾å°å¯¹åºè®ç»æ°æ®è¾å¥½çåæ°ãåé¢çlog2c,log2gåå«è®¾ç½®Cårçæç´¢èå´ãæç´¢æºå¶æ¯ä»¥2为åºææ°æç´¢ï¼å¦ âlog2c â3 , 3,1 å°±æ¯åæ°C,ä»2^-3ï¼2^-2ï¼2^-1â¦æç´¢å°2^3.
æç´¢å°è¾å¥½åæ°åï¼å¨è®ç»çæ¶åå ä¸åæ°ç设置ã
å¦å¤ï¼è¯»è å¯ä»¥èªå·±è¯è¯æ°æ®é2,3.