How to find large prime numbers for RSA with the Miller-Rabin Primality Test

Posted on August 12, 2018 in Security, Cryptography • Tagged with Python, Primes, Math, RSA, asymmetric key cryptography, Miller-Rabin Primality Test, Fermat • 11 min read


All sources for this blog post can be found in the Github repository about large primes. The most recent version of the sources may only be found in the Github repository.

It has been a long time since I found the energy to write a new blog post. In this article, I am going to dig into a interesting area of cryptography: The task to find large prime numbers. We hopefully are all familiar with the concept of prime numbers. Prime numbers are integers \(p\) which are dividable only by \(p\) itself and \(1\). But why is it necessary to find large prime numbers in the area of cryptography?

One of the first asymmetric cryptosystems invented was RSA (1977). As all public key algorithms, the security of RSA depends on the existence of a one-way function.

In the case of RSA, the one-way function is built on top of the integer factorization problem: Given two prime numbers \(p,q\in \mathbb{N}\), it is straightforward to calculate \(n=p \cdot q\), but it is computationally infeasible to reverse this multiplication by finding the factors \(p\) and \(q\) given the product \(n\). Even when the primes \(p\) and \(q\) are …

Continue reading

Solution for wargame natas19

Posted on September 15, 2015 in Php • Tagged with Python, Wargames, Php, Security • 3 min read

Hi everyone

I am still trying to solve wargames on overthewire. Level 19 proofed to be very similar to level 18, where server side code looks something like the following:


$maxid = 640; // 640 should be enough for everyone

function isValidAdminLogin() { /* {{{ */
    if($_REQUEST["username"] == "admin") {
    /* This method of authentication appears to be unsafe and has been disabled for now. */
        //return 1;

    return 0;
/* }}} */
function isValidID($id) { /* {{{ */
    return is_numeric($id);
/* }}} */
function createID($user) { /* {{{ */
    global $maxid;
    return rand(1, $maxid);
/* }}} */
function debug($msg) { /* {{{ */
    if(array_key_exists("debug", $_GET)) {
        print "DEBUG: $msg";
/* }}} */
function my_session_start() { /* {{{ */
    if(array_key_exists("PHPSESSID", $_COOKIE) and isValidID($_COOKIE["PHPSESSID"])) {
        if(!session_start()) {
            debug("Session start failed");
            return false;
        } else {
            debug("Session start ok");
            if(!array_key_exists("admin", $_SESSION)) {
                debug("Session was old: admin flag set");
                $_SESSION["admin"] = 0; // backwards compatible, secure
            return true;

    return false;
/* }}} */
function print_credentials() { /* {{{ */
    if($_SESSION and array_key_exists("admin", $_SESSION) and $_SESSION["admin"] == 1) {
        print "You are an admin. The credentials for the next level are:";
        print "Username: natas19n";
        print "Password: ";  
    } else {  
        print "You are logged in as a regular user. Login as an admin to retrieve credentials for natas19.";  
/* }}} */

$showform = true;  
if(my_session_start()) {  
    print_credentials …

Continue reading

Cross platform Lichess Cheat

Posted on August 12, 2015 in Chess • Tagged with Software, Python, Programming, Chess • 5 min read

Edit: Cheat updated on 1.10.2015

Visit Lichess Bot Projects Page for the newest information for this bot! The description and code below will probably not work anymore!

Hello Everyone

Once in a while I like to play Chess on lichess. But sometimes I get beat up tot harshly, such that I want to take some revenge :D. Recently I created a new cheat for lichess. You can find the whole source code on my lichess cheat github repository. If you want to use the cheat, please follow the following tutorial:

  1. Download and install Python 3.4 (or newer) for your operating system from here: python web site
  2. Add Python to your system path such that you can open python file from anywhere (This step depends on what operating system you are using)
  3. Then download the python cheat from here. It is the file with the .py suffix
  4. Then execute the python cheat file where you downloaded it. Just go to the directory where you saved it and enter in a shell: `python
  5. Open your browser (tested with chrome and firefox) and add the HTTP proxy server in the network settings that is outputted in the …

Continue reading

A lot of work to do for GoogleScraper in the future and request for comments!

Posted on March 01, 2015 in Googlescraper • Tagged with Software, Python, Programming, Googlescraper • 3 min read

Hello dear readers

I get a lot of mail regarding questions about GoogleScraper. I really appreciate them, but at some stage I cannot answer them anymore. In the last weeks I didn't have a lot of time (and motivation I must admit) to put into GoogleScraper.

The reason is, that I am still unconfortable with the architecture of GoogleScraper. There are basically two ways to use the tool:

  • As a command line tool
  • From another program over the API (programming approach)

and furthermore there are 3 very different modes GoogleScraper runs in:

  • http mode
  • selenium mode which again can be divided in Firefox, Chrome and PhantomJS selenium browsers
  • asynchronous mode

whereas I think that selenium is the hardest to work with (very buggy and complex to program in). This leads to a complex software architecture, mainly because the two operational modes (CLI tool and API) have different priorities of how to handle exceptions.

The CLI tool should be VERY robust and it should to everything it can to continue scraping with the remaining ressources (like proxies, RAM, when lots of selenium instances become an issue, networking bandwith, ...), because the user cannot handle these problems by himself when he calls GoogleScraper …

Continue reading

Scraping and Extracting Links from any major Search Engine like Google, Yandex, Baidu, Bing and Duckduckgo

Posted on November 12, 2014 in Meta • Tagged with Scraping, Baidu, Extracting, Google, Programming, Python, Searchengine, Bing, Meta • 7 min read


It's been quite a while since I worked on my projects. But recently I had some motivation and energy left, which is quite nice considering my full time university week and a programming job besides.

I have a little project on GitHub that I worked on every now and again in the last year or so. Recently it got a little bit bigger (I have 115 github stars now, would've never imagined that I ever achieve this) and I receive up to 2 mails with job offers every week (Sorry if I cannot accept any request :( ).

But unfortunately my progress with this project is not as good as I want it to be (that's probably a quite common feeling under us programmers). It's not a problem of missing ideas and features that I want to implement, the hard part is to extend the project without blowing legacy code up. GoogleScraper has grown evolutionary and I am waisting a lot of time to understand my old code. Mostly it's much better to just erease whole modules and reimplement things completely anew. This is essentially what I made with the parsing module.

Parsing SERP pages with many search engines

So I …

Continue reading

Socks 5 client support for twisted

Posted on February 05, 2014 in Programming • Tagged with Python, Twisted, Socks5, Programming, Security • 5 min read

I recently forked twisted-socks to add SOCKS 5 support for my GoogleScraper in order to scraper Google pages asynchronously. Obviously I needed SOCKS5 support to anonymize the parallel requests such that I can scrape more pages simultaneously.

I tested the code for SOCKS4 and SOCKS4a with a local TOR proxy and twistd -n socks and the SOCKS5 protocol with the dante socks proxy server on my VPS. So I guess the basic functionality should be working by now. GSSAPI (Kerberos) support is planned.

Here is the socksclient code, which is also available on my github repository:

# Copyright (c) 2011-2013, The Tor Project
# See LICENSE for the license.

# Updated on 25.01.14-28.01.14 to add SOCKS 5 support.
# Cleaned some parts of the code and abstracted quite a bit to handle the most important SOCKS5
# functionality like
# - username/password authentication
# - gssapi authentication (planned)
# - CONNECT command (the normal case, there are others: UDP ASSOCIATE and BIND, but they aren't as important. Maybe I will add them
#   in the future. If anyone wants to implement them, the basic structure is already here and the SOCKSv5ClientProtocol should be
#   rather easy extensible (how the actual connection, listening for incoming connections (BIND) and …

Continue reading