|
Chris Pollett >
Students >
Molina
( Print View)
[Bio]
[Blog]
[CS 297 Proposal]
[Deliverable 1]
[Deliverable 2]
[Deliverable 3]
[Deliverable 4]
[McEliece System]
[Regev System]
[RSA System]
[CS 297 Report-PDF]
[CS 298 Proposal]
[CS298 Slides-PDF]
[CS298 Report-PDF]
|
Implementing the md5 hash function
Michaela Molina (michaela.molina@sjsu.edu)
Purpose:
The purpose of this deliverable was to get more experience programming with Rust. By coding the md5 hash function I acquired proficiency in language constructs including mutability, structs, String slices, references, modules, borrowing, array slices, scope, string formatting, match statements, function pointers, which types are allocated on the stack, which types are allocated on the heap, vectors, function pointers, pointers, and converting between integer types such as u8, u32, and usize.
Md5 hash function implementation:
The code works as follows. First, I convert a character string to a binary string using the characters' ascii values. Then I add a single "1" bit to the message followed by enough "0"s to make its length congruent to 448 mod 512. Then I create a 64-bit binary string representing the length of the original message and append the lower-order 32 bits followed by the higher order 32 bits to the message.
Following this I divide the message into groups of 32 bits and create a new vector of decimal numbers each of which represents a 32-bit number. I initialize 4 32-bit registers. Then I process groups of 16 words at a time. For every block of 16 words I perform four round functions on the block. These round functions perform various operations on the values of the registers using the values from the block, modifying the registers as they go. When all of the groups are processed, I add the initial values of the four registers to the resulting values of the four registers. The values of these registers in binary, concatenated, form the value of the hash function.
Code: Md5 hash function
main.rs
mod util;
use md5;
use std::f64::consts::PI;
use std::collections::HashMap;
use random_string::{
Charset,
GenResult,
generate,
};
fn main() {
let charset = Charset::new("1234567890abcdefghijklmnopqrstuvw
xyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()-_+=[]{}\\|;:'\"/?>.<,`~").unwrap();
let mut results = HashMap::new();
// test on 500 strings each of length 50, 100, and 300
let mut lengths = vec![50,100,300,500];
for length in &lengths {
for i in 0..500 {
let mut random_string = generate(*length as usize, &charset);
let mut message = format!("{}", random_string);
let mut my_hash = hash(message.clone());
let rust_hash = format!("{:x}", md5::compute(message.clone()));
let mut result = false;
if my_hash.eq(&rust_hash) {
result = true;
}
if !results.contains_key(&result) {
results.insert(result, 1);
} else {
let mut count = results[&result].clone();
count += 1;
results.insert(result, count);
}
} // end for i in 100
} // end for length in lengths
for (result, count) in &results {
println!("{} => {}", result, count);
}
}
fn hash(message:String) -> String {
let mut bin_string = util::character_string_to_binary_string(&message.clone());
let mut length_as_64_bit_binary_string = util::get_length_as_64_bit_binary_string(&bin_string);
util::pad_binary_string(&mut bin_string);
let mut words = util::create_words(&bin_string); // words is a vector of u32
let mut i = 0;
let mut word1 = &length_as_64_bit_binary_string[32..64];
let mut word2 = &length_as_64_bit_binary_string[0..32];
let mut w1 = util::binary_string_to_dec(&word1);
let mut w2 = util::binary_string_to_dec(&word2);
words.push(w1);
words.push(w2);
let mut a:u32 = 1732584193;
let mut b:u32 = 4023233417;
let mut c:u32 = 2562383102;
let mut d:u32 = 271733878;
let t = construct_t();
for i in (0..words.len()).step_by(16) {
let block = &words[i..i+16];
let aa = a;
let bb = b;
let cc = c;
let dd = d;
round_one (&mut a, &mut b, &mut c, &mut d, block, t);
round_two (&mut a, &mut b, &mut c, &mut d, block, t);
round_three(&mut a, &mut b, &mut c, &mut d, block, t);
round_four (&mut a, &mut b, &mut c, &mut d, block, t);
let base:u64 = 2;
a = ((a as u64 + aa as u64) % (base.pow(32))) as u32;
b = ((b as u64 + bb as u64) % (base.pow(32))) as u32;
c = ((c as u64 + cc as u64) % (base.pow(32))) as u32;
d = ((d as u64 + dd as u64) % (base.pow(32))) as u32;
//print_registers(&mut a, &mut b, &mut c, &mut d);
}
let mut byte1 = format!("{:x}", reverse_bytes_in_word(a));
let mut byte2 = format!("{:x}", reverse_bytes_in_word(b));
let mut byte3 = format!("{:x}", reverse_bytes_in_word(c));
let mut byte4 = format!("{:x}", reverse_bytes_in_word(d));
while byte1.len() < 8 { byte1.insert(0, '0'); }
while byte2.len() < 8 { byte2.insert(0, '0'); }
while byte3.len() < 8 { byte3.insert(0, '0'); }
while byte4.len() < 8 { byte4.insert(0, '0'); }
let mut hash = String::new();
hash.push_str(&byte1);
hash.push_str(&byte2);
hash.push_str(&byte3);
hash.push_str(&byte4);
hash
}
fn reverse_bytes_in_word(dec:u32) -> u32 {
let mut binary = format!("{:b}", dec);
while (binary.len() < 32) {
binary.insert(0,'0');
}
let mut byte1 = &binary[0..8];
let mut byte2 = &binary[8..16];
let mut byte3 = &binary[16..24];
let mut byte4 = &binary[24..32];
let mut result = String::new();
result.push_str(byte4);
result.push_str(byte3);
result.push_str(byte2);
result.push_str(byte1);
util::binary_string_to_dec(&result)
}
fn print_registers(a:&mut u32,
b:&mut u32,
c:&mut u32,
d:&mut u32) {
println!("A = {}, B = {}, C = {}, D = {}", a,b,c,d);
}
fn round_one(a:&mut u32,
b:&mut u32,
c:&mut u32,
d:&mut u32, block:&[u32], t:[u32;64]) {
let x_index = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
let bitshift = [7,12,17,22];
let t_index = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16];
for i in 0..16 {
match i%4 {
0 => round(f,a,*b,*c,*d,x_index[i], bitshift[i%4], t_index[i],block,t),
1 => round(f,d,*a,*b,*c,x_index[i], bitshift[i%4], t_index[i],block,t),
2 => round(f,c,*d,*a,*b,x_index[i], bitshift[i%4], t_index[i],block,t),
3 => round(f,b,*c,*d,*a,x_index[i], bitshift[i%4], t_index[i],block,t),
_ => println!(""),
};
}
}
fn round_two(a:&mut u32,
b:&mut u32,
c:&mut u32,
d:&mut u32, block:&[u32], t:[u32;64]) {
let x_index = [1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12];
let bitshift = [5,9,14,20];
let t_index = [17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32];
for i in 0..16 {
match i%4 {
0 => round(g,a,*b,*c,*d,x_index[i], bitshift[i%4], t_index[i],block,t),
1 => round(g,d,*a,*b,*c,x_index[i], bitshift[i%4], t_index[i],block,t),
2 => round(g,c,*d,*a,*b,x_index[i], bitshift[i%4], t_index[i],block,t),
3 => round(g,b,*c,*d,*a,x_index[i], bitshift[i%4], t_index[i],block,t),
_ => println!(""),
};
}
}
fn round_three(a:&mut u32,
b:&mut u32,
c:&mut u32,
d:&mut u32, block:&[u32], t:[u32;64]) {
let x_index = [5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2];
let bitshift = [4,11,16,23];
let t_index = [33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48];
for i in 0..16 {
match i%4 {
0 => round(h,a,*b,*c,*d,x_index[i], bitshift[i%4], t_index[i],block,t),
1 => round(h,d,*a,*b,*c,x_index[i], bitshift[i%4], t_index[i],block,t),
2 => round(h,c,*d,*a,*b,x_index[i], bitshift[i%4], t_index[i],block,t),
3 => round(h,b,*c,*d,*a,x_index[i], bitshift[i%4], t_index[i],block,t),
_ => println!(""),
};
}
}
fn round_four(a:&mut u32,
b:&mut u32,
c:&mut u32,
d:&mut u32, block:&[u32], t:[u32;64] ) {
let x_index = [0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9];
let bitshift = [6,10,15,21];
let t_index = [49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64];
for i in 0..16 {
match i%4 {
0 => round(i_,a,*b,*c,*d,x_index[i], bitshift[i%4], t_index[i],block,t),
1 => round(i_,d,*a,*b,*c,x_index[i], bitshift[i%4], t_index[i],block,t),
2 => round(i_,c,*d,*a,*b,x_index[i], bitshift[i%4], t_index[i],block,t),
3 => round(i_,b,*c,*d,*a,x_index[i], bitshift[i%4], t_index[i],block,t),
_ => println!(""),
};
}
}
fn f(x:u32,y:u32,z:u32) -> u32 {
(x & y) | ((!x) & z)
}
fn g(x:u32,y:u32,z:u32) -> u32 {
(x & z) | (y & !z)
}
fn h(x:u32,y:u32,z:u32) -> u32 {
x ^ y ^ z
}
fn i_(x:u32,y:u32,z:u32) -> u32 {
y ^ (x | !z)
}
fn round(aux: fn(u32,u32,u32) -> u32,
a:&mut u32, b:u32, c:u32, d:u32,
x_index:usize, bitshift:u32, t_index:usize,
x:&[u32], t:[u32; 64]) {
let base:u64 = 2;
let inner_sum:u64 = *a as u64 + aux(b,c,d) as u64 + x[x_index] as u64 + t[t_index-1] as u64;
let modded_inner_sum:u64 = inner_sum % base.pow(32);
let modded_inner_sum_u32:u32 = modded_inner_sum as u32;
let rotated_quantity = rotate_left(bitshift as usize, modded_inner_sum_u32);
let b_sum = rotated_quantity as u64 + b as u64;
let final_sum:u32 = (b_sum % base.pow(32)) as u32;
*a = final_sum;
}
pub fn rotate_left(i:usize,n:u32) -> u32 {
let mut s = format!("{:b}", n);
while s.len() < 32 {
s.insert(0,'0');
}
let first = &s[0..i];
let second = &s[i..];
let mut shifted = String::new();
shifted.push_str(second);
shifted.push_str(first);
util::binary_string_to_dec(&shifted)
}
pub fn construct_t() -> [u32; 64] {
let mut T:[u32;64] = [0;64];
T[0]=3614090360;
T[1]=3905402710;
T[2]=606105819;
T[3]=3250441966;
T[4]=4118548399;
T[5]=1200080426;
T[6]=2821735955;
T[7]=4249261313;
T[8]=1770035416;
T[9]=2336552879;
T[10]=4294925233;
T[11]=2304563134;
T[12]=1804603682;
T[13]=4254626195;
T[14]=2792965006;
T[15]=1236535329;
T[16]=4129170786;
T[17]=3225465664;
T[18]=643717713;
T[19]=3921069994;
T[20]=3593408605;
T[21]=38016083;
T[22]=3634488961;
T[23]=3889429448;
T[24]=568446438;
T[25]=3275163606;
T[26]=4107603335;
T[27]=1163531501;
T[28]=2850285829;
T[29]=4243563512;
T[30]=1735328473;
T[31]=2368359562;
T[32]=4294588738;
T[33]=2272392833;
T[34]=1839030562;
T[35]=4259657740;
T[36]=2763975236;
T[37]=1272893353;
T[38]=4139469664;
T[39]=3200236656;
T[40]=681279174;
T[41]=3936430074;
T[42]=3572445317;
T[43]=76029189;
T[44]=3654602809;
T[45]=3873151461;
T[46]=530742520;
T[47]=3299628645;
T[48]=4096336452;
T[49]=1126891415;
T[50]=2878612391;
T[51]=4237533241;
T[52]=1700485571;
T[53]=2399980690;
T[54]=4293915773;
T[55]=2240044497;
T[56]=1873313359;
T[57]=4264355552;
T[58]=2734768916;
T[59]=1309151649;
T[60]=4149444226;
T[61]=3174756917;
T[62]=718787259;
T[63]=3951481745;
T
}
util.rs
pub fn create_words(s:&String) -> Vec<u32> {
let mut words = Vec::new();
let mut word = String::new();
for c in s.chars() {
word.push(c);
if word.len() == 32 {
word = reverse_bytes(&word);
words.push(binary_string_to_dec(&word));
word.clear();
}
}
words
}
pub fn reverse_bytes(w:&String) -> String {
let mut new_word = String::new();
let mut bytes:Vec<String> = Vec::new();
for i in (0..w.len()).step_by(8) {
let mut byte = &w[i..i+8];
bytes.push(String::from(byte));
}
bytes.reverse();
for byte in &bytes {
new_word.push_str(byte);
}
new_word
}
pub fn character_string_to_binary_string(s:&String) -> String {
let mut result = String::new();
for b in s.as_bytes() {
let mut byte = format!("{:b}", b);
while byte.len() < 8 {
byte.insert(0,'0');
}
result.push_str(&byte);
}
result
}
// input: binary string representing message
pub fn get_length_as_64_bit_binary_string(s:&String) -> String {
let mut result = format!("{:b}", s.len());
while result.len() < 64 {
result.insert(0,'0');
}
result
}
pub fn pad_binary_string(s:&mut String) {
s.push('1');
while s.len() % 512 != 448 {
s.push('0');
}
}
pub fn binary_string_to_dec(s:&str) -> u32 {
let mut result:u32 = 0;
let base:u32 = 2;
let len:u32 = s.len() as u32;
for (i,c) in s.chars().enumerate() {
let index:u32 = i as u32;
let exp:u32 = len-index-1;
if c=='1' {
result += base.pow(exp);
}
}
result
}
Cargo.toml
[package]
name = "md5"
version = "0.1.0"
authors = ["Michaela Molina <michaela.molina&sjsu.edu>"]
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
md5 = "0.7.0"
to-binary = "0.4.0"
random-string = "0.2.0"
|