Category Archives: Technical

Verifying the signature of linux kernel using gpg

Digital signatures functions as the electronic equivalent of  handwritten signatures. It can be used to authenticate the source of data as well as verify its identity.

Linux kernel releases are signed by the person who makes the release. This signature helps us in verifying whether the files have been tampered by any intruder. The process of signing and verification uses public-key cryptography.

All Linux kernel releases are cryptographically signed by OpenPGP compliant signatures. PGP signatures would be hard to forge since the attacker requires the private key of the developer who made the release. We can verify the integrity of the downloaded version of kernel using GPG.

Step 1:

Fetch the source code and the corresponding signature key from

$ wget
$ wget

Uncompress the tar file.

unxz linux-3.1.5.tar.xz

Step 2:

Verify the signature of the downloaded kernel

$ gpg --verify linux-3.1.5.tar.sign

Signature made Friday 09 December 2011 10:46:46 PM IST using RSA key ID 6092693E
gpg: Can't check signature: public key not found

Step 3:

In order to accomplish our task of verifying, we need to get the public key from PGP Keyserver with the help of RSA key ID that we got 6092693E .

$ gpg --recv-keys 6092693E
gpg: requesting key 6092693E from hkp server
gpg: /home/sowcat/.gnupg/trustdb.gpg: trustdb created
gpg: key 6092693E: public key "Greg Kroah-Hartman (Linux kernel stable release signing key) <>" imported
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)

 Step 4:

Now verify the signature again:

$ gpg --verify linux-3.1.5.tar.sign
gpg: Signature made Friday 09 December 2011 10:46:46 PM IST using RSA key ID 6092693E
gpg: Good signature from "Greg Kroah-Hartman (Linux kernel stable release signing key) <>"
gpg: WARNING: This key is not certified with a trusted signature!
gpg:          There is no indication that the signature belongs to the owner.
Primary key fingerprint: 647F 2865 4894 E3BD 4571  99BE 38DB BDC8 6092 693E

The signature seems to be a Good Signature! This means that the public key that we got earlier belongs to the person who made the release.
Instead of gpg: Good signature from “Greg Kroah-Hartman, if it was BAD signature, then:
1) It could be because of incomplete download
2) The downloaded file is not truncated
3) The files might be corrupted

Even though our verification says ‘Good signature’, we can see a warning. This because we did not verify whether the key comes from the person ‘Greg’.
One way of checking is by mailing the people in the list of signature ask them to check if the signature can be trusted. We can see the list of signature by entering the command gpg --list-sigs. Another way is checking with the Kernel web of trust.

This seems to be  a long task to verify the authenticity. So, it is better to ignore the warning and trust the signature.



Encrypting and decrypting a file with symmetric key

This post explains how to encrypt and decrypt a file using symmetric key. In symmetric algorithms the security depends on the strength of the key as the encryption and decryption key is the same. The strength of the key depends on the key size. Key size is the number of bits in the key. This key has to be agreed by both the sender and receiver before the communication starts. The security of the algorithm depends on the secrecy of the key.

Consider a file ‘secret.txt’ with the following content

Secret key is 98234

Now, we encrypt it with a symmetric key using gpg.

gpg --symmetric secret.txt

This asks for a pass-phrase, which is the key.
The cipher algorithm used here is CAST5. CAST5(or CAST-128) is a block cipher. Block ciphers divides the message into blocks and each block is encrypted at a time. The key used for encrypting each block is the same. CAST5 has a fixed block size of 8 bytes. You can read more about CAST5 here.

Now, the encrypted file ‘secret.txt.gpg’ is created.
The content of secret.txt.gpg is:

<8c>^M^D^C^C^BÊÏñT<96>ÅGc`É1    7NA!áW<95>i^Y<98>s1 -lÐ^\j°ã[;$qs^GsÛ^?^<9d>    /n<99>ÞÜ<87>äâýD,^OM£¸ù

To decrypt, type the following command

gpg --decrypt secret.txt.gpg

This outputs the following

gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
Secret key is 98234
gpg: WARNING: message was not integrity protected

Symmetric keys are useful when to protect any files in your own PC.


Gpg Key-Pair Encryption and Decryption

Using GPG we can generate private and public keys which can be used to encrypt and decrypt files. Here, the private key should be kept confidential. Even if the public key is made available, the message cannot be decrypted.

Consider a person A wants to send a secret message to person B. B’s public key is known to A and A encrypts the message using this. However, this encrypted message can be decrypted only by B since B alone knows the private key.

Let’s see how to generate a key pair and thereby performing encryption and decryption.

Step 1: Key pair generation

$ gpg --gen-key
gpg (GnuPG) 1.4.11; Copyright (C) 2010 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
Your selection? 1
RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048) 3000
Requested keysize is 3000 bits
rounded up to 3008 bits
Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 5
Key expires at Wednesday 23 January 2013 07:01:08 PM IST
Is this correct? (y/N) y

You need a user ID to identify your key; the software constructs the user ID
from the Real Name, Comment and Email Address in this form:
"Heinrich Heine (Der Dichter) <>"

Real name: sowmya
Email address:
Comment: This is my OS assignment
You selected this USER-ID:
"sowmya (This is my OS assignment) <>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? O
You need a Passphrase to protect your secret key.

The Passphrase that we provide is our private key.

We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

Not enough random bytes available.  Please do some other work to give
the OS a chance to collect more entropy! (Need 171 more bytes)

Not enough random bytes available.  Please do some other work to give
the OS a chance to collect more entropy! (Need 63 more bytes)
gpg: key 014D1F5E marked as ultimately trusted
public and secret key created and signed.

gpg: checking the trustdb
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
gpg: next trustdb check due at 2013-01-23
pub   3008R/014D1F5E 2013-01-18 [expires: 2013-01-23]
      Key fingerprint = 26AE 91CA E577 C4C4 F168  16D5 4A83 6C5D 014D 1F5E
uid                  sowmya (This is my OS assignment) <>
sub   3008R/D39FA9A6 2013-01-18 [expires: 2013-01-23]

014D1F5E is our public key.

Step 2: Exporting the key

gpg --export > sowmya-pub.gpg
gpg --armor --export > sowmya-pub-asc.gpg

Importing other’s public key

gpg --import FileName

Send encrypted message

gpg --recipient 'public_key' --armor --encrypt secret.txt

Decrypt the encrypted message

Consider a file ‘secret.txt’ which is encrypted as secret.txt.asc. To decrypt secret.txt.asc:

$ gpg --decrypt secret.txt.asc > secret.txt

You need a passphrase to unlock the secret key for
user: "sowmya (This is my OS assignment) <>"
3008-bit RSA key, ID D39FA9A6, created 2013-01-18 (main key ID 014D1F5E)

gpg: encrypted with 3008-bit RSA key, ID D39FA9A6, created 2013-01-18
      "sowmya (This is my OS assignment) <>"


Deadlock Characterization

There are some necessary conditions for deadlock to happen. They are:

1. Mutual Exclusion: Only process at a time can use the resource. Suppose p1 is holding the resource. If another process p2 requests for this resource, p2 is kept waiting. p2 is delayed until resource is released.

2. Hold and Wait: Here the process is holding one resource and it wants to acquire additional resources. These additional resources are held by other processes. So this process holds some resources and waits for other resources to be released.

3. No preemption: Resources cannot be preempted. A process must give away it’s resources voluntarily after it has done it’s job.

4. Circular Wait: Consider p0,p1,p2 all are waiting processes. p0 waits for a resource held by p1, p1 waits for resource held by p2 and p2 waits for resource held by p0.

We could predict deadlocks by using graphs called Resource Allocation Graphs.

Deadlock – Getting Started

Well, I hope the readers have some idea about process synchronization. You may refer my friend’s blog to understand about mutual exclusion problem and use of semaphore much clearly.

All-rite! so let’s start with Deadlock. Consider a multiprogramming environment. Here several processes compete for finite number of resources. What if one process P1 waits for a resource R1 which is currently held by some other process P2? P1 enters into a waiting state. There are chances that P1 never enters the ready state since the resources it needs are always occupied by some other process. Such a situation is referred as deadlock.

Silberschatz book explains this with a beautiful example. Consider a system with 3 CD drives and 3 processes. Suppose each of the process holds one of these CD Drives, and they now request for CD Drive held by some other process. Here the 3 processes will be in a deadlock state. Let’s discuss with some more example.

Consider this pthread program.

void *one(void *arg)
  /* D0 $0me Task */



void *two(void *arg)
    /* D0 $0me Task */



Now assume two threads are created. Both of them have access to both the mutex_locks. Thread1 runs in function ‘one’, thread2 runs in function ‘two’. So, thread_one acquires lock in the order first_mutex and second mutex. Whereas thread_two acquires lock in the order second_mutex and first_mutex. This is an example for deadlock where both keeps waiting to acquire the lock. (thread_1 attempts to lock mutex_one whereas thread_2 attempts to lock mutex_two.)

Lets discussion the Deadlock characterization in the next post.

Insertion Sort

Input: sequence of n nos a1,a2,a3…
Output: permutation of those numbers such that a1′<=a2′<=a3′..
It’s an effective algo for sorting small no of elements.

Find the correct position and the insert it
To find the correct position we compare with the nos already present
Check with each element. The whole array would be sorted after the process. i.e, check with each element and insert it before or after.

So It takes in i/p an array of n elements A[1-n] in sorted order
During insertion, the nos are rearranged within the array and sorted.

void insertion_sort(int unsorted[],int number_of_elements)
 int i,j,key;
while(i>0 && unsorted[i]>key)

Just an example
5 | 2 | 4 | 6 | 1 | 3 |
Key = 2 unsorted[j]
unsorted[i]>key, 5>2
unsorted[i+1]=unsorted[i], unsorted[2]=unsorted[1]=5
i=i-1=0, unsorted[i+1]=key=2

2 | 5 | 4 | 6 | 1 | 3 |
2 | 4 | 5 | 6 | 1 | 3 |
1 | 2 | 4 | 5 | 6 | 3 |    in loop. Checks with all previous elements
1 | 2 | 3 | 4 | 5 | 6 |

Complete implementation can be found at

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

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++)
    for(int j=i+1;j<number_of_elements;j++)

      unsorted[i]=unsorted[minimum_position] ;

Complete implementation of the code can be found at