Selection Sort

Here we find the smallest element in the list and swap it with the first element. Then the second smallest, swapping with second element and so on. This is done till (n-1) times. And number of swaps required is n-1.

5 4 3 2 1
1 4 3 2 5
1 2 3 4 5
1 2 3 4 5
Well, the time complexity is O(n*n) which is same as https://sowmyaravidas.wordpress.com/2012/10/06/bubble-sort/

But selection is better since number of swaps required is less.

void selection_sort(int unsorted[],int number_of_elements)
{
int minimum;
int temp;
int minimum_position;
for(int i=0;i<number_of_elements;i++)
   {
    minimum=unsorted[i];
    for(int j=i+1;j<number_of_elements;j++)
    {
     if(minimum>unsorted[j])
     {
      minimum=unsorted[j];
      minimum_position=j;

      temp=unsorted[i];
      unsorted[i]=unsorted[minimum_position] ;
      unsorted[minimum_position]=temp;
      }
    }
  }
}

Complete implementation of the code can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

Advertisements

Bubble Sort

This is a brute force method of sorting.  Compare the successive elements from position 1 to last. This is one
iteration. Do till (n-1) times.

5 4 3 2 1
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
This is iteration1. So at the end, maximum element moves to the end.

The time complexity of this algorithm is O(n*n).


 void bubble_sort(int unsorted[],int n)
 {
     int temp;
    for(int i=0;i<number_of_elements-1;i++)
    {
       for(int j=0;j<number_of_elements-i-1;j++)
       {
            if(unsorted[j]>unsorted[j+1])
             {
                 temp=unsorted[j];
                 unsorted[j]=unsorted[j+1];
                 unsorted[j+1]=temp;
             }
        }
     }

Complete implementation can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

DareYourMind: MorseCode

 

So this is the Question:

We don’t get any clue with this pic. But analyse it carefully. It contains some morse code.

.– . .-.. -.. -.. — -. . – …. . .–. .- … … .– — .-. -.. .. … … .- — ..- . .-.. — — .-. … .

Then the problem becomes easier. Decode it using http://www.onlineconversion.com/morse_code.htm
And you will get the password 🙂

 

DareYourMind: Md5 crack

Question: http://www.dareyourmind.net/menu.php?page=crypto5

You are provided with a picture and you need to crack the md5 of it.

Well … Just try saving the pic. By default it will be saved with md5 value as the name.
We could try decrypting it using http://www.md5decrypter.co.uk/. This would give you the solution 😀

 

Fermats Factorizing method

This is a really nice algorithm to find out factors of an odd integer, which could be represented as the difference
between two squares. This algorithm works even when n is a large integer.  So, this could be an easy way to determine p and q in RSA decryption when n is sufficiently large.

Method:

Given a number n.
Fermat’s factorization methods look for integers x and y such that n=x^2-y^2. Then it can be represented as

 n=(x-y)(x+y)
(1)

and n is factored.

Every positive odd integer can be represented in the form n=x^2-y^2 by writing n=ab (with a>b) and noting that this gives

a = x+y
(2)
b = x-y.
(3)

Adding and subtracting,

a+b = 2x
(4)
a-b = 2y,
(5)

so solving for x and y gives

x = 1/2(a+b)
(6)
y = 1/2(a-b).
(7)

Therefore,

 x^2-y^2=1/4[(a+b)^2-(a-b)^2]=ab.

Consider an example:

Let, n=15
So, n can be represented as:

n=4^2 – 1^2

n=(4+1)(4-1) = 5*3
a=4+1
b=4-1
a+b=2*4
a-b=2*1
x=4
y=1
x=1/2(a+b) = 4
y=1/2(a-b) = 1
x^2 – y^2 = 16 – 1 = 15 = ab.

source: http://mathworld.wolfram.com/FermatsFactorizationMethod.html

OverTheWire-Krypton:Level 2

Now, ssh krypton2@krypton.labs.overthewire.org
The password is R****N.

Level Info:

Krypton 2

Substitution ciphers are a simple replacement algorithm. In this example of a substitution cipher, we will explore a ‘monoalphebetic’ cipher. Monoalphebetic means, literally, “one alphabet” and you will see why.

This level contains an old form of cipher called a ‘Caesar Cipher’. A Caesar cipher shifts the alphabet by a set number. For example:

plain: a b c d e f g h i j k … cipher: G H I J K L M N O P Q …

In this example, the letter ‘a’ in plaintext is replaced by a ‘G’ in the ciphertext so, for example, the plaintext ‘bad’ becomes ‘HGJ’ in ciphertext.

The password for level 3 is in the file krypton3. It is in 5 letter group ciphertext. It is encrypted with a Caesar Cipher. Without any further information, this cipher text may be difficult to break. You do not have direct access to the key, however you do have access to a program that will encrypt anything you wish to give it using the key. If you think logically, this is completely easy.

One shot can solve it!

Have fun.

Alrite! Question seems to be a bit long. So we need to perform caesar shift to get the password.
The file Krypton3 contains the encrypted password: OMQEMDUEQMEK
Use the code https://sowmyaravidas.wordpress.com/2012/09/15/encryption-code-for-caesar-cipher/ here
with proper indentation to decrypt it. This helps you generate all the possibilities:
PNRFNEVFRNFL
QOSGOFWGSOGM
RPTHPGXHTPHN
SQUIQHYIUQIO
TRVJRIZJVRJP
USWKSJAKWSKQ
VTXLTKBLXTLR
WUYMULCMYUMS
XVZNVMDNZVNT
YWAOWNEOAWOU
ZXBPXOFPBXPV
AYCQYPGQCYQW
BZDRZQHRDZRX
CAESARISEASY
DBFTBSJTFBTZ
ECGUCTKUGCUA
FDHVDULVHDVB
GEIWEVMWIEWC
HFJXFWNXJFXD
IGKYGXOYKGYE
JHLZHYPZLHZF
KIMAIZQAMIAG
LJNBJARBNJBH
MKOCKBSCOKCI
NLPDLCTDPLDJ

You got the password for next level!!

OverTheWire-Krypton: Level 1

Level Info:

The password for level 2 is in the file ‘krypton2’. It is ‘encrypted’ using a simple rotation. It is also in non-standard ciphertext format. When using alpha characters for cipher text it is normal to group the letters into 5 letter clusters, regardless of word boundaries. This helps obfuscate any patterns. This file has kept the plain text word boundaries and carried them to the cipher text. Enjoy!

Ok!
krypton1@melissa:/krypton/krypton1$ cat krypton2
YRIRY GJB CNFFJBEQ EBGGRA
So this is the encoded text. It is encrypted using a simple rotation. ROT13.
When you do ROT13 (shift the letters by 13), the text decodes to LEVEL TWO PASSWORD R****N
Whoa! We got the password for Level2:  R****N