| Home | Sign up! | Projects | Seminars | Research Notes | Today's Lecture | About |
Kulmeet KaurEmail
kulmeetk@yahoo.com
| Profile: Bachelor in Computer Applications. (Graduated in April 2003)
Diploma in Management & Information Technology (August 2004)
Masters in Science(Information Systems) from Tarleton State University, TX.
Have worked as a Graduate Research Assistant for Deptt of Mathematics, Physics & Engg.
Currently working as a Business Analyst in Los Angeles, US.
Encryption, Compression and Error-Correction
Master’s Thesis
by
Kulmeet Kaur
Thesis Supervisor
Prof. Ashay Dharwadker
Ansal Institute of Technology
15th April 2004
Abstract
This thesis is a survey of some of the widely used methods of data encryption,
file compression and error-correction used on most computers and networks.
These important algorithms are incorporated in operating systems for file
storage and as part of the TCP/IP protocol suite that drives the Internet.
We study and implement three famous algorithms: RSA Encryption, Huffman
coding for file compression and the Hamming code for error-correction.
Each algorithm is implemented in C++ using the client-server paradigm to
be run over a computer network. The source code of the software is provided
under the GNU public license for noncommercial use on the accompanying
CD.
Contents
1. Introduction
2. Project topics
2.1. RSA Encryption
2.1.1. Introduction
2.1.2. History
2.1.3. About Rivest, Shamir, Adleman
2.1.4. About the original paper
2.1.5. Caveats
2.2. Hamming Code for error detection and correction
2.2.1. Introduction
2.2.2. History
2.2.3. About Hamming
2.2.4. About the original paper
2.2.5. Caveats
2.3. Huffman coding-data compression
2.3.1. Introduction
2.3.2. History
2.3.3. About Huffman
2.3.4. About the original paper
2.3.5. Caveats
2.4. Client-Server
2.4.1. Introduction
2.4.2. Use of client-server application
using the three topics mentioned above
2.5. TCP/IP
2.6. Reason for interest in the project
3. Code (programs)
4. Analysis and explanation of the code
5. References |
Prof. Ashay Dharwadker's Courses (3): | Course | Semester | Grade | | | MS Project | Fall 2003 | View | | | Database Systems | Fall 2003 | View | | | Computer Networks | Spring 2004 | View | |
|
Project ID: 17
Course: Database Systems
Topic: Online shopping database
| Description: This project is a joint venture by Deepika Saxena and I.The database proposed to be prepared is expected to exhibit a online shopping database.
The database to be prepared and compiled under this topic include:-
1.list of all the products available for purchase.
2.list of orders placed by customers(date-wise ie. according to the date they placed an order on).An order_ID will be assigned to each order with the help of auto-increment; this will help the customer in checking the status of the order.
3.each order will be assigned a unique order no., so that the customer can check the status of the order.
The look of the project-
My SQL will be used to prepare the backend
and the front end will be a MS-Access spreadsheet.
Primary keys of each table-
Table Primary Key
Product Table item_name
Order Table order_id
Technologies used for this project are-
MySQL, php programming and HTML or MS Access
for latest update on this project,please refer to Deepika's account
Database created-Creating database andTables in MySQL (commands,fields,etc)
create database online_shopping;
create table product(pid integer not null,company_name char(20),description char(20),market_price integer,max_you_pay integer,item_name char(10),primary key(pid));
create table orders(oid integer not null,customer_name char(20),account_no integer,email_id char(20),age integer,sex char(1),mobile_no integer,date char(10),primary key(oid));
create table category(cid integer not null,category char(20),primary key(cid));
create table po(pid integer not null,oid integer not null,status char(10),primary key(pi,cid),foreign key(pid)references product,foreign key(oid) references orders);
create table pc(cid integer not null,pid integer not null,no_of_pieces integer,primary key(cid,pid),foreign key(cid)references category,foreign key(pid)references product);
The above mentioned database ie. online_shopping can be viewed at PC no.15 in Lab 1. |
Project ID: 18
Course: MS Project
Topic: Encryption, Compression and Error correction
| Description: The RSA Encryption is one of the most popular encryption method. Till now I have studied the method to convert the data bit into 128 bit using private and public keys(prime no.).To encrypt data using RSA Encryption, the algorithm is defined by R-Rivest, S-Shamir & A-Adleman.
The algorithm-
1. Select primes to be assigned to P,Q (normally they should be large numbers to avoid hacking).
2. Find E such that:-
(i)E>1 & is odd
(ii)gcd(E,(P-1)(Q-1))=1
3.Find D such that:-
(D*E)%(P-1)(Q-1)=1
Now. the actual encryption starts,-
for encryption-Encrypt(T)=pow(T,E)%PQ ,where T stands for text.
for decrytpion-Derypt(C)=pow(C,D)%PQ where C is the encrypted form of the actual text.
Finally, after completion of RSA enryption, we get the encrypted data, the public key (E,PQ)and the private key D
Vectors will be used to do long number computations.The arithmetic operations to be performed to do encryption are-
Addition(+)
Multiplication(*)
Subtraction(-)
power(^)
Modulo(%)
These comptutations are to be performed on large numbers, that is why we need to define the process (otherwise, these are predefined functions (for small numbers) in the library files) As far as the programs are concerned (for computations) few programs are written.
The programs give the desired number and the count of digits in that number,like for-
1000th fibonacci number take 209 digits and 10000th takes 2090 digits.
The project work has completed the initial research for the method to encrypt, now the programming part has to be undertaken. For programming, Visual C++ will be used.
For programming references-Essential C++ by Stanley Lippman
Regarding Compreesion and Error Correction, refer to research notes for Huffman coding (File Compression) and Hamming Codes ( Error Correction). |
Seminar ID: 8
Course: MS Project
Topic: RSA Encryption
| Description: My seminar will basically include information about my project .I'll be highlighting the calculations involved in the compuation of 128 bit pattern.The mathematical calculations used will work towards making the encryption formula simpler and increase the efficiency of the program.
During the seminar, programs to find the factorial of a number, fibonacci series, etc were run and they dealt with large numbers for which the methods and variable types were to be defined as the pre-defined ones couldn't handle these large numbers. |
Seminar ID: 23
Course: Database Systems
Topic: Error Detection and Correction Codes
| | Description: Seminar by-Deepika Saxena and Kulmeet K.
While transmission of data, due to certain reasons data is lost or data transmitted generates errors and incorrect data reaches the destination.To detect these errors error detection codes are used.As the errors are detected error correction codes are used to remove the errors, so that the receiver gets the correct data(as far as possible).At times, it is errors don't get removed as there are certain flaws in these codes.
The process is done with the help of information transmitted alongwith the data from the source.When the destination receivec the data the additional information is used to detect the error and also to correct it.Various codes like CRC,Parity check, hamming's code,golay's code etc are available for this purpose.
Basically a brief introduction to the codes with detailed description of hamming and golay's code will be covered during the seminar.The flaws in these codes will be highlighted during the seminar.
Seminar schedule-
Time-11:30 a.m.
Date-Nov.25,2003
Venue-Computer Lab-I
AIT,Gurgaon |
Seminar ID: 48
Course: Computer Networks
Topic: Hamming codes ( Error Detection & correction Codes)
| Description: Hamming Code for Error Detection & Correction Codes was invented by Richard Hamming. This error detection and Correction method detects and corrects a single-bit error.
Hamming Code Algorithm-
While transmitting the data-
1. Take ASCII value of the character.
2. Add 64 to the ASCII value.
3. Compute the binary equivalent of the sum..
4. Break the binary into two parts, each of 4-bits..
5. Locate the obtained two 4-bit binary numbers in the table (Hamming codes) and
replace them with corresponding hamming code words..
6. Transmit the code words.
.
While receiving the data-.
1. For each 7-bit data received, hamming distance is calculated with respect to each codeword present in the table..
2. The codeword, which gives the 1 as hamming distance is the correct code word that should have been received..
3. The last three bits are removed from the correct codeword..
4. Remaining 4-bits form the data word..
5. Obtain the 4-bit data word from the two consecutive code words (corrected) and combine them together..
6. The data word obtained is the corrected error-free word..
Example-
Data word to be transmitted- A
ASCII value of ‘A’- 65.
Add 64.
Value obtained= 65+64=129
Binary equivalent of 129=10000001
Two 4-bit parts- 1000
0001
Hamming code for- 1000 is 1000110
0001 is 0001011
On receiving error occurs, say, instead of 1000110 we receive 1000010
, and instead of 0001011 we receive 1001011
After computing the hamming distance, we get the corrected codewords and after removing the right-most 3 bits we get, 1000 and 0001.
As we combine the two we get, 10000001 which is equal to 129=’A’.
Using the table created for Hamming code, one can detect and correct the error in the code, if any.
|
Research Note ID: 31
Course: Database Systems
Topic: The Golden Rule
| Description:
The first version-
"No update opertaions must be ever allowed to leave any relvar in a state that violates its own predicate"
It applies to all the relvars,derived as well as base.Relvar stands for relational variable.There are two predicates -internal(formal) which is understood by both user and the system,and external(informal) which is understood by the user but not by the system.
The Golden Rule (extended) is-
"No update operation must ever be allowed to leave any relvar in a state that violates its own predicate.Likewise,no update transaction must ever be allowed to leave the database in a state that violates it own predicate."
Each relvar has an associated predicate ,so does every database-the database predicate,which is defined as the logical AND of all database and relvar constraints that apply to the database in question.
The rule is not widely supported though in principle it is quite straightforward.
Reference-C.J.Date,"An Introduction to Database Systems". |
Research Note ID: 51
Course: MS Project
Topic: Huffman Coding (File Compression)
| Description: When a file or data is tranmitted over a medium or better known as channel, it needs to be compressed. This is required to save the transmission time.For this various compression methods are available, like Huffman Encoding.
The Huffman encoding method uses tree (data structure) to do the actual encoding and hence compression.
HUFFMAN CODING
To start the procedure or coding, first a tree structure is formed.This is done by first finding the frequency of each alphabet existing in the text or data.These frequencies are plcaed in a line at the bottom of the tree.Then the least two values are added to form a new level or node which is known as the parent node of the two numbers (least) added which are known as the children nodes.Following the procedure, a tree structure is formed and at the top of the tree ie the root holds the value which represents the size of the data or the alphabet occurence frequencies total.
Then the children nodes of the root node are assigned 0 and 1 respectively ie left child is assigned 0 and right child is assigned 1.Moving downwards to each child node is assigned value in correspondence to its parent node ie the value of parent node is considered for children nodes by adding 0 and 1 at the end of the parent node value ie suffix 0 and 1 to parent node value respectively for left child and right child.
Example-Suppose parent node value is 100, then the left child value will be 1000 and right child value is 1001.
After the values are asigned to each node, the are assigned to the alphabets in the frequency table.The value is associated by tracking down the intial frequency tree to the exact node holding the value.The value or the codeword or huffman code is the value of the leaves ie. the nodes which donot have any children.
Example:-
the data to be transmitted is-ENQUIRE
Steps-
1.Make frequency table.
Frequency-table
Alaphabet Frequency
E 2 00
N 1 01
Q 1 100
U 1 101
I 1 110
R 1 111
2.Make binary tree and try maintaining levels.
4.Label the nodes using combinations of 0s and 1s as per huffman coding rule (mentioned earlier).
5.Assign each alphabet the corresponding binary numbers.
6.Transmit the message-
ENQUIRE as
000110010111011100
For decoding
7.When the message is received by the receiver, it is decoded.Each binary number is picked and compared with the codeords assigned to each alphabet.Next binary digit is suffixed in case the previous one doesn't match any in the table.
for more information, please click on the link-
www.nist.gov |
Research Note ID: 78
Course: Computer Networks
Topic: Berkeley Sockets
| Description: In client-server applications, sockets are required to set up the connection over the network. Socket is a communiction protocol. To start with connection setting and message transmission, primitives are used.These are -
1. Socket.
2.Bind
3.Accept.
4.Listen
5.Write
6.Connect.
7.Read.
Sockets are used by API( Application Program Interface) in client-server applications.
History-
refer to the link below
http://encyclopedia.thefreedictionary.com/Berkeley%20sockets
for reference, click on the link-http://www.nd.edu/~lemmon/courses/UNIX/l6/node3.html |
|
Last updated on Thursday, 7th September 2006, 10:56:15 AM.
Prof. Ashay Dharwadker
|
|
