Hack is fun

I choose to be a hacker just because it's fun.

Programming • Penetration • Reverse • Sectool
  • Programming

    Show me the code.

  • Penetration

    Know it and hack it.

  • Reverse

    Everything can be pwn.

  • Sectool

    Sharp tools make good work.

sunnyelf

python实现基于埃拉托斯特尼筛法快速生成素数的优化

作者: 分类: 学习记录 评论: 暂无 时间: 2017-03-26 浏览: 111 次

0x00 埃拉托斯特尼筛法

埃拉托斯特尼筛法,也就是我们常说的素数筛选法的一种方法:

0x02 优化

使用了python的生成器方法生成一个超大的字典,这样做的方法是为了减少内存的消耗,循环只需到n的平方根square_root就行了,然后测试一下,最大的8位数基本40s能求出所有质因子。用到一些小优化,在python 2 中while 1:要比while True:要快,if value:要比if value == True:,不相信的话可以测试一下,然后看一下它们生成的操作码,另外大数计算中最好不用for循环,而用while循环。

0x02 实现

#!/usr/bin/env python
# coding=utf-8
# author:admin[@hackfun.org]
# license:GPL v3
# blog:hackfun.org

def gen_super_dict(n):
    """use python generator to generate super dictionary and save memory"""
    i = 2 # 0 and 1 is not prime
    while 1:
        if i > n:
            break
        yield i
        i += 1

def gen_prime_list(n):
    """use prime screen method to generate all prime numbers less than n"""
    super_dict = {}
    primes_list = []

    for x in gen_super_dict(n):
        super_dict[x] = True

    i = 2
    while 1:
        if i > n:
            break
        j = i * i
        while 1:
            if j >= n:
                break
            if super_dict[i]:
                super_dict[j] = False
            j += i
        i += 1

    for key,value in super_dict.items():
        if value:
            primes_list.append(key)
    return primes_list

python实现基于米勒拉宾素性检测算法最快的超大数素性检测

作者: 分类: 学习记录 评论: 暂无 时间: 2017-03-26 浏览: 85 次

0x00 米勒拉宾素性检测算法伪代码

米勒拉宾素性检测算法的伪代码:

Input #1: n > 3, an odd integer to be tested for primality;
Input #2: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime

write n − 1 = (2 ^ r) * d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then
      continue WitnessLoop
   repeat r − 1 times:
      x ← x^2 mod n
      if x = 1 then
         return composite
      if x = n − 1 then
         continue WitnessLoop
   return composite
return probably prime

0x01 实现

一开始针对这个米勒拉宾素性检测算法里的幂模运算,我以为用蒙哥马利算法-快速幂模要比pow()函数更快,结果还是内置的pow()更快:

# x = a^d n n
def montgomery(a, d, n):
    x = 1
    while d:
        if (d & 1):
            x = (x * a) % n
        d >>= 1  
        a = (a * a) % n
    return x

上面的伪代码中a的选取是可以优化的,可以看到下面代码有实现,原理看一下wikipedia

def select_a_list(n):
    if n < 2047:
        return [2,]
    elif n < 1373653:
        return [2, 3]
    elif n < 9080191:
        return [31, 73]
    elif n < 25326001:
        return [2, 3, 5]
    elif n < 3215031751:
        return [2, 3, 7]
    elif n < 4759123141:
        return [2, 7, 61]
    elif n < 1122004669633:
        return [2, 13, 23, 1662803]
    elif n < 2152302898747:
        return [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        return [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        return [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    elif n < 3317044064679887385961981:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    else:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

0x02 测试

用这个方法检测素数,100位10进制数平均0.0003,1000位10进制数平均0.09秒,10000位10进制数平均60秒。

0x03 完整代码

#!/usr/bin/env python
# coding=utf-8
# author:admin[@hackfun.org]
# license:GPL v3
# blog:hackfun.org

def select_a_list(n):
    if n < 2047:
        return [2,]
    elif n < 1373653:
        return [2, 3]
    elif n < 9080191:
        return [31, 73]
    elif n < 25326001:
        return [2, 3, 5]
    elif n < 3215031751:
        return [2, 3, 7]
    elif n < 4759123141:
        return [2, 7, 61]
    elif n < 1122004669633:
        return [2, 13, 23, 1662803]
    elif n < 2152302898747:
        return [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        return [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        return [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    elif n < 3317044064679887385961981:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    else:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def calc_r_d(n):
    n -= 1
    r = 0
    d = n
    while 1:
        if n % 2 != 0:
            break
        r += 1
        d = n / 2
        n /= 2
    return r, d

def miller_rabin_primality_test(n):
    """use miller rabin primality test to judge n whether prime"""
    if n < 0:
        n = -n
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    r, d = calc_r_d(n)
    a_list = select_a_list(n)
    for k in xrange(len(a_list)):
        a = random.sample(a_list, 1)[0] # Select one non-repeating random number from the list at a time
        a_list.remove(a)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for t in xrange(r - 1):
            x = pow(x, 2, n)
            if x ==1:
                return False
            if x == n - 1:
                break
        else:
            return False
    return True

浅析弱口令

作者: 分类: 渗透测试 评论: 2条 时间: 2017-03-16 浏览: 11,211 次

浅析弱口令.png

0x00 前言

弱口令其实是长期以来一直存在的问题,直到今天我们还能经常听某个著名厂商公司因为存在弱口令问题而导致大量内部或外部用户信息泄露,甚至商业计划和机密泄露,所以一个安全密码设置的重要性不言而喻,涉及密码,不得谈到密码的强弱,当然强弱密码的区分没有一个严格明确的定义,通常认为容易被别人(他们有可能对你很了解)猜测到或容易被破解工具破解的口令均为弱密码,在此我粗略谈谈弱密码方面,也就是我们经常说到的弱口令。

其实设置密码的强弱很大程度上与这个人的个人习惯和安全意识有关,当然还是受其他的因素的影响,比如公司出于安全考虑要求设置强密码等其他强制硬性要求,个人觉得弱口令可以大致分为两类,一类就是公共弱口令,另一类就是个人弱口令。

阅读全文»

尽最大可能分析上传源码及漏洞利用方式

作者: 分类: 渗透测试 评论: 暂无 时间: 2017-03-03 浏览: 6,882 次

0x00 简单源码分析

<?php
if ((($_FILES["file"]["type"] == "image/gif")       //检测Content-type值
|| ($_FILES["file"]["type"] == "image/jpeg")
|| ($_FILES["file"]["type"] == "image/pjpeg"))
&& ($_FILES["file"]["size"] < 20000))              //检测文件大小
  {
  $ext = end(explode('.', $_FILES["file"]["name"]));  //获取最后“.”的后缀
  if($ext === 'php')                          //检测是否为php后缀
    {
    exit('error');
    }
  if ($_FILES["file"]["error"] > 0)           //返回上传错误码
    {
    echo "Return Code: " . $_FILES["file"]["error"] . "<br />";
    }
  else                                                  //返回上传成功信息
    {
    echo "Upload: " . $_FILES["file"]["name"] . "<br />";
    echo "Type: " . $_FILES["file"]["type"] . "<br />";
    echo "Size: " . ($_FILES["file"]["size"] / 1024) . " Kb<br />";
    echo "Temp file: " . $_FILES["file"]["tmp_name"] . "<br />";

    if (file_exists("upload/" . $_FILES["file"]["name"]))  //检测文件是否存在
      {
      echo $_FILES["file"]["name"] . " already exists. ";
      }
    else                          //将上传的临时文件转移到指定存放文件夹
      {
      move_uploaded_file($_FILES["file"]["tmp_name"],
      "upload/" . $_FILES["file"]["name"]);
      echo "Stored in: " . "upload/" . $_FILES["file"]["name"];
      }
    }
  }
else
  {
  echo "Invalid file";              //返回无效文件的错误信息
  }
?>

阅读全文»

一道有趣的网络取证分析CTF题目

作者: 分类: CTF 评论: 1条 时间: 2017-02-28 浏览: 3,831 次

0x01 解题

这是一道新颖的网络取证分析的题目,用TCP协议紧急数据来隐藏发送flag,很多选手都被其中的图片带偏了方向,导致花了很多时间也没有做出来,其实刚开始我也被带入坑:-(

阅读全文»