Snippets

Alexander Hanel CryptoPals

Updated by Alexander Hanel
View revision

File solutions.md Modified

  • Ignore whitespace
  • Hide word diff 
 
  - https://dbjergaard.github.io/posts/matasano_set_1.html 
   - Recommends chi-squared. Cool concept but super slow in Python. Would not recommend it. 
-  - [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 
-  - [Chi-square distribution introduction | Probability and Statistics | Khan Academy](https://www.youtube.com/watch?v=dXB3cUGnaxQ)
-  - [Pearson's chi square test (goodness of fit) | Probability and Statistics | Khan Academy ](https://www.youtube.com/watch?v=2QeDRsxSF9M)
+ - [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 
+ - [Chi-square distribution introduction | Probability and Statistics | Khan Academy](https://www.youtube.com/watch?v=dXB3cUGnaxQ)
+ - [Pearson's chi square test (goodness of fit) | Probability and Statistics | Khan Academy ](https://www.youtube.com/watch?v=2QeDRsxSF9M)
 
 chi-squared approach 
 
         chi, tt = chisquare(temp_freq, expected)
         print chi, tt, temp
 ```        
-            
-    
+ - Classic approach - https://inventwithpython.com/hacking/chapter20.html
Updated by Alexander Hanel
View revision

File solutions.md Modified

  • Ignore whitespace
  • Hide word diff 
 ```
 
 
- - https://dbjergaard.github.io/posts/matasano_set_1.html recommends chi-squared. Cool concept but super slow in Python. Would not recommend. 
+ - https://dbjergaard.github.io/posts/matasano_set_1.html 
+  - Recommends chi-squared. Cool concept but super slow in Python. Would not recommend it. 
   - [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 
   - [Chi-square distribution introduction | Probability and Statistics | Khan Academy](https://www.youtube.com/watch?v=dXB3cUGnaxQ)
   - [Pearson's chi square test (goodness of fit) | Probability and Statistics | Khan Academy ](https://www.youtube.com/watch?v=2QeDRsxSF9M)
Updated by Alexander Hanel
View revision

File solutions.md Modified

  • Ignore whitespace
  • Hide word diff 
 ```
 ### Challenge 4  - Detect single-character XOR
  - Solution using limited frequency analysis approach
+
 ```Python
 import string
 from collections import Counter
 
 chi-squared approach 
 
- ```Python
+```Python
 import math
 import string
Updated by Alexander Hanel
View revision

File solutions.md Modified

  • Ignore whitespace
  • Hide word diff 
 ```
 
 
- - https://dbjergaard.github.io/posts/matasano_set_1.html
- - [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 
- - [Chi-square distribution introduction | Probability and Statistics | Khan Academy](https://www.youtube.com/watch?v=dXB3cUGnaxQ)
- - [Pearson's chi square test (goodness of fit) | Probability and Statistics | Khan Academy ](https://www.youtube.com/watch?v=2QeDRsxSF9M)
+ - https://dbjergaard.github.io/posts/matasano_set_1.html recommends chi-squared. Cool concept but super slow in Python. Would not recommend. 
+  - [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 
+  - [Chi-square distribution introduction | Probability and Statistics | Khan Academy](https://www.youtube.com/watch?v=dXB3cUGnaxQ)
+  - [Pearson's chi square test (goodness of fit) | Probability and Statistics | Khan Academy ](https://www.youtube.com/watch?v=2QeDRsxSF9M)
+
+chi-squared approach 
+
+ ```Python
+import math
+import string
+
+from collections import Counter
+from itertools import cycle
+
+
+# Source http://jsbin.com/kaxoxajige/1/edit?js,output
+expected = [0.08167,0.01492,0.02782,0.04253,0.12702,0.02228,0.02015,0.06094,0.06966,0.00153,0.00772,
+0.04025,0.02406,0.06749,0.07507,0.01929,0.00095,0.05987,0.06327,0.09056,0.02758,0.00978,
+0.02360,0.00150,0.01974,0.00074]
+
+
+# Source -h https://hflog.wordpress.com/2014/04/01/how-to-perform-a-chi-squared-goodness-of-fit-test-in-python
+
+def gf(x):
+    #Play with these values to adjust the error of the approximation.
+    upper_bound=100.0
+    resolution=1000000.0    
+    step=upper_bound/resolution
+    val=0
+    rolling_sum=0
+    while val<=upper_bound:
+        rolling_sum+=step*(val**(x-1)*2.7182818284590452353602874713526624977**(-val))
+        val+=step
+    return rolling_sum
+
+
+def ilgf(s,z):
+    val=0
+    for k in range(0,100):
+        val+=(((-1)**k)*z**(s+k))/(math.factorial(k)*(s+k))
+    return val
+
+    
+def chisquarecdf(x,k):
+    return 1-ilgf(k/2,x/2)/gf(k/2)
+
+
+def chisquare(observed_values,expected_values):
+    test_statistic=0
+    for observed, expected in zip(observed_values, expected_values):
+        test_statistic+=(float(observed)-float(expected))**2/float(expected)
+    df=len(observed_values)-1
+    return test_statistic, chisquarecdf(test_statistic,df)
+
+
+def frequency(message):
+    message = message.lower().strip(" ")
+    freq = []
+    length = len(message)
+    for char in "abcdefghijklmnopqrstuvwxyz":
+        freq.append(float(message.count(char)) / length)
+    return freq
+
+
+def xor_mb(message, key):
+        return''.join(chr(ord(m_byte)^ord(k_byte)) for m_byte,k_byte in zip(message, cycle(key)))
+
+
+printset = set(string.printable)
+messages = open("4.txt", 'r').readlines()
+
+
+for line in messages:
+    message = line.rstrip().decode('hex')
+    for key in range(0 ,256):
+        temp = xor_mb(message, chr(key))
+        temp_freq = frequency(temp)
+        chi, tt = chisquare(temp_freq, expected)
+        print chi, tt, temp
+```        
+            
+    
+
+
Updated by Alexander Hanel
View revision

File solutions.md Modified

  • Ignore whitespace
  • Hide word diff 
 		print key, xor_mb(message, key)
 ```
 ### Challenge 4  - Detect single-character XOR
- - Solution non-frequency analysis approach
+ - Solution using limited frequency analysis approach
 ```Python
 import string
 from collections import Counter
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.