Secure Hashing Algorithm

A C and C++ Implementation

The Secure Hashing Standard, defined in FIPS PUB 180-1, defines the Secure Hashing Algorithm (SHA-1). SHA-1 can be used to produce a message digest for a given message. Essentially, this is a 160-bit number that represents the message.

In theory, no two messages would ever share the same message digest. What this means is that the message digest can serve as a fingerprint for a file or other source of data. SHA-1 is used by Digital Signature Standard (DSS), which is a standard used for digitally signing documents or other data.

From this page, you can download the C++ and the C the implementations of SHA-1. This is the same source base from which the code in RFC 3174 was based. While the RFC has remained static, this code base has been modified (ever so slightly) and any reported bug fixes will be put into this source repository. (To date, none have been reported, though the code has been used widely.)

Along with the class that implements the SHA-1 algorithm, there are also utilities to produce fingerprints of files, compare files based on fingerprints, and exercise the class itself.

You can also download binary versions for Linux and Windows. These include the utilities "sha" and "shacmp" for displaying fingerprints of files (sha) and also comparing the fingerprints of two files (shacmp).

The fingerprint for the C++ (sha1.zip) file is: 46067CBB 52E86D16 2C66818E EBD0B682 886F4B12

The fingerprint for the C (sha1-c.zip) file is: 569BE022 AEF78867 3263F05E 07B015F2 9D7D5553

The fingerprint for the Linux binaries (sha1_linux.tgz) file is: CA4CC3EA C3E92261 18196B13 1C138DF3 A4C6E0DB

Windows binaries are in the sha1.zip file.

Finally, we should point out that this is not an optimized version of the SHA-1 algorithm. It is written so that the algorithm can be easily compared against the FIPS document. No effort has been made to improve performance in any way.

If you are looking for an optimized version, may we suggest you use Christophe Devine's code. It can be found here. Our preliminary testing shows that it is significantly faster than the reference implementation found on this page.

If you have any questions or comments, feel free to contact Paul Jones.

Selection Sort

Algorithm Analysis
The selection sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled. The selection sort has a complexity of O(n2).
Pros: Simple and easy to implement.Cons: Inefficient for large lists, so similar to the more efficient insertion sort that the insertion sort should be used in its place.
Source CodeBelow is the basic selection sort algorithm.
void selectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;
for (i = 0; i < array_size-1; i++)
{
min = i;
for (j = i+1; j < array_size; j++)
{
if (numbers[j] < numbers[min])
min = j;
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}

Quick Sort

Algorithm Analysis
The quick sort is an in-place, divide-and-conquer, massively recursive sort. As a normal person would say, it's essentially a faster in-place version of the merge sort. The quick sort algorithm is simple in theory, but very difficult to put into code (computer scientists tied themselves into knots for years trying to write a practical implementation of the algorithm, and it still has that effect on university students).
The recursive algorithm consists of four steps (which closely resemble the merge sort):
If there are one or less elements in the array to be sorted, return immediately.
Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
Recursively repeat the algorithm for both halves of the original array.
The efficiency of the algorithm is majorly impacted by which element is choosen as the pivot point. The worst-case efficiency of the quick sort, O(n2), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn't random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(n log n).
Pros: Extremely fast.Cons: Very complex algorithm, massively recursive.
Source CodeBelow is the basic quick sort algorithm.
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}

Merge Sort

Algorithm Analysis
The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).
Elementary implementations of the merge sort make use of three arrays - one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don't yield any significant performance enhancement over the recursive algorithm on most machines.
Pros: Marginally faster than the heap sort for larger sets.Cons: At least twice the memory requirements of the other sorts; recursive.
Source CodeBelow is the basic merge sort algorithm.
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}

Insertion Sort

Algorithm AnalysisThe insertion sort works just like its name suggests - it inserts each item into its proper place in the final list. The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.
Like the bubble sort, the insertion sort has a complexity of O(n2). Although it has the same complexity, the insertion sort is a little over twice as efficient as the bubble sort.
Pros: Relatively simple and easy to implement.Cons: Inefficient for large lists.
Source CodeBelow is the basic insertion sort algorithm.
void insertionSort(int numbers[], int array_size)
{
int i, j, index;
for (i=1; i < array_size; i++)
{
index = numbers[i];
j = i;
while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}

Bubble Sort

Algorithm AnalysisThe bubble sort is the oldest and simplest sort in use. Unfortunately, it's also the slowest.
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.
The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n2).
While the insertion, selection, and shell sorts also have O(n2) complexities, they are significantly more efficient than the bubble sort.
Pros: Simplicity and ease of implementation.Cons: Horribly inefficient.
Source CodeBelow is the basic bubble sort algorithm.
void bubbleSort(int numbers[], int array_size)
{
int i, j, temp;
for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}

Matlab code example computing index for a single letter image

% %letterdemo.m
% This Matlab program takes as input
% a letter image and a letter mask image and
% illustrates the computation of the letter image statistics for
% the readability index of Scharff and Ahumada (2003).
% mask for the letter e
mask = ...
[ 0 0 0 0
0 1 1 0
1 0 0 1
1 1 1 1
1 0 0 0
1 0 0 1
0 1 1 0
0 0 0 0];

% letter e simulated luminance image
% imageY = floor(100*rand(size(mask))+50*mask);
imageY =...
[ 81 83 79 87
66 106 145 73
84 37 52 63
78 120 138 51
84 54 17 89
103 44 97 69
72 119 77 29
30 62 25 66];
%number of text pixels
nmask = sum(mask(:)); % 13
% average text pixel luminance
avetxt = sum(mask(:).*imageY(:))/nmask; % 95.1538
% variance of the text pixel luminance
vtxt = sum(mask(:).*(imageY(:)-avetxt).^2)/nmask;% 786.5917
% number of background pixels
nbck = sum(1-mask(:)); % 19
% average background luminance
avebck = sum((1-mask(:)).*imageY(:))/nbck; % 60.1579
% variance of background luminance
vbck = sum((1-mask(:)).*(imageY(:)-avebck).^2)/nbck; % 551.5014
% proportion of text pixels
pT = nmask/(nmask+nbck);
% To obtain the Global masking index of Scharff, Hill, and Ahumada (2000)
% pT = 0 ;
qT = 1-pT; % 0.4063 0.5937
% contrast of the text with respect to the background
CT = avetxt/avebck - 1;% 0.5817
% contrast of the text with respect to the image average
CA = qT*CT/(pT*CT+1); % 0.2794
% variance of the image contrast
vTB = ((pT*vtxt+qT*vbck)/avebck^2+pT*qT*CT^2)/(pT*CT+1)^2;% 0.1704
% image contrast adjusted by the masking variance relative to the
% contrast masking threshold C2
C2 = 0.05;
index = CA/sqrt(1+vTB/C2^2); %0.0336