Last active
April 12, 2025 21:09
-
-
Save HarryR/87314550fcbae361010e2bfee1995066 to your computer and use it in GitHub Desktop.
Poly1305 implementation & test vector print-out in pure Rust
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ ./bin/poly1305.native.exe | |
2.5.2. Poly1305 Example and Test Vector | |
For our example, we will dispense with generating the one-time key | |
using AES, and assume that we got the following keying material: | |
o Key Material: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01:0 | |
3:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b | |
o s as an octet string: | |
01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b | |
Nir & Langley Informational [Page 15] | |
RFC 7539 ChaCha20 & Poly1305 May 2015 | |
o s as a 128-bit number: 1bf54941aff6bf4afdb20dfb8a800301 | |
o r before clamping: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8 | |
o Clamped r as a number: 806d5400e52447c036d555408bed685 | |
For our message, we'll use a short text: | |
Message to be Authenticated: | |
000 43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f Cryptographic Fo | |
016 72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f rum Research Gro | |
032 75 70 up | |
Since Poly1305 works in 16-byte chunks, the 34-byte message divides | |
into three blocks. In the following calculation, "Acc" denotes the | |
accumulator and "Block" the curren | |
Block #1 | |
Acc = 00 | |
Block = 6f4620636968706172676f7470797243 | |
Block with 0x01 byte = 16f4620636968706172676f7470797243 | |
Acc + block = 16f4620636968706172676f7470797243 | |
(Acc+Block) * r = | |
2c88c77849d64ae9147ddeb88e69c83fc | |
Acc = ((Acc+Block)*r) % P = 2c88c77849d64ae9147ddeb88e69c83fc | |
Block #2 | |
Acc = 2c88c77849d64ae9147ddeb88e69c83fc | |
Block = 6f7247206863726165736552206d7572 | |
Block with 0x01 byte = 16f7247206863726165736552206d7572 | |
Acc + block = 37febea505c820f2ad5150db0709f96e | |
(Acc+Block) * r = | |
2d8adaf23b0337fa7cccfb4ea344b30de | |
Acc = ((Acc+Block)*r) % P = 2d8adaf23b0337fa7cccfb4ea344b30de | |
Last Block | |
Acc = 2d8adaf23b0337fa7cccfb4ea344b30de | |
Block = 17075 | |
Block with 0x01 byte = 17075 | |
Acc + block = 2d8adaf23b0337fa7cccfb4ea344ca153 | |
(Acc+Block) * r = | |
28d31b7caff946c77c8844335369d03a7 | |
Acc = ((Acc+Block)*r) % P = 28d31b7caff946c77c8844335369d03a7 | |
Nir & Langley Informational [Page 16] | |
RFC 7539 ChaCha20 & Poly1305 May 2015 | |
Adding s, we get this number, and serialize if to get the tag: | |
Acc + s = 2a927010caf8b2bc2c6365130c11d06a8 | |
Tag = a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9 | |
Usage: poly1305 <data1> [data2] [data3] ... | |
$ ./bin/poly1305.native.exe hello world | |
e9854fe8f9656900d6d3e3032000c66a |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// SPDX-License-Identifier: MIT | |
// https://cr.yp.to/mac/poly1305-20050329.pdf | |
// https://www.rfc-editor.org/rfc/rfc7539.txt | |
const DEFAULT_KEY_MATERIAL: [u8; 32] = [ | |
0x85, 0xd6, 0xbe, 0x78, 0x57, 0x55, 0x6d, 0x33, 0x7f, 0x44, 0x52, 0xfe, 0x42, 0xd5, 0x06, 0xa8, | |
0x01, 0x03, 0x80, 0x8a, 0xfb, 0x0d, 0xb2, 0xfd, 0x4a, 0xbf, 0xf6, 0xaf, 0x41, 0x49, 0xf5, 0x1b, | |
]; | |
pub trait P1305Field: Sized + Copy { | |
fn zero() -> Self; | |
fn from_u128_clamped(value: u128) -> Self; | |
fn from_u128(value: u128) -> Self; | |
fn to_hex_string(&self) -> String; | |
fn mark(&self) -> Self; | |
fn add(&self, other: Self) -> Self; | |
fn mul(&self, other: Self) -> Self; | |
fn reduce(&self) -> Self; | |
fn to_u128(&self) -> u128; | |
} | |
pub struct Poly1305<F: P1305Field> { | |
h: F, | |
r: F, | |
s: u128, | |
buffer: Vec<u8>, | |
buffer_used: usize, | |
} | |
#[derive(Clone, Copy, PartialEq, Debug)] | |
pub struct P1305u64(u64, u64, u64); | |
#[inline] | |
const fn u128_to_u64x2(t: u128) -> (u64, u64) { | |
( | |
(t & 0xFFFF_FFFF_FFFF_FFFF) as u64, | |
((t >> 64) & 0xFFFF_FFFF_FFFF_FFFF) as u64, | |
) | |
} | |
impl<F: P1305Field> Poly1305<F> { | |
pub fn new(key: &[u8; 32]) -> Self { | |
let mut r_bytes = [0u8; 16]; | |
let mut s_bytes = [0u8; 16]; | |
r_bytes.copy_from_slice(&key[0..16]); | |
s_bytes.copy_from_slice(&key[16..32]); | |
Self { | |
h: F::zero(), | |
r: F::from_u128_clamped(u128::from_le_bytes(r_bytes)), | |
s: u128::from_le_bytes(s_bytes), | |
buffer: Vec::with_capacity(16), | |
buffer_used: 0, | |
} | |
} | |
pub fn update(&mut self, data: &[u8]) { | |
let mut index = 0; | |
// If we have data in the buffer, try to fill it | |
if self.buffer_used > 0 { | |
while index < data.len() && self.buffer_used < 16 { | |
self.buffer.push(data[index]); | |
index += 1; | |
self.buffer_used += 1; | |
} | |
// If we filled the buffer, process it | |
if self.buffer_used == 16 { | |
let mut block = [0u8; 16]; | |
block.copy_from_slice(&self.buffer[0..16]); | |
self.process_block(&block, false); | |
self.buffer.clear(); | |
self.buffer_used = 0; | |
} | |
} | |
// Process complete blocks | |
while index + 16 <= data.len() { | |
let mut block = [0u8; 16]; | |
block.copy_from_slice(&data[index..(index + 16)]); | |
self.process_block(&block, false); | |
index += 16; | |
} | |
// Store remaining bytes in buffer | |
while index < data.len() { | |
self.buffer.push(data[index]); | |
index += 1; | |
self.buffer_used += 1; | |
} | |
} | |
fn process_block(&mut self, block: &[u8; 16], partial: bool) { | |
// Core Poly1305 operation: h = (h + block) * r | |
let b = F::from_u128(u128::from_le_bytes(*block)); | |
let b = if partial { b } else { b.mark() }; | |
self.h = self.h.add(b).mul(self.r).reduce(); | |
} | |
pub fn finalize(&mut self) -> [u8; 16] { | |
// Process any remaining data in the buffer with the padding bit | |
if self.buffer_used > 0 { | |
let mut block = [0u8; 16]; | |
// Copy buffer contents to block | |
for i in 0..self.buffer_used { | |
block[i] = self.buffer[i]; | |
} | |
// Set the padding bit (0x01) at the appropriate position | |
block[self.buffer_used] = 0x01; | |
self.process_block(&block, true); | |
} | |
// Add 's' to the accumulator and return the result | |
self.h.to_u128().wrapping_add(self.s).to_le_bytes() | |
} | |
} | |
impl P1305Field for P1305u64 { | |
#[inline] | |
fn zero() -> Self { | |
Self(0, 0, 0) | |
} | |
#[inline] | |
fn mark(&self) -> Self { | |
Self(self.0, self.1, self.2 | (1 << 40)) | |
} | |
#[inline] | |
fn from_u128(t: u128) -> Self { | |
let (t0, t1) = u128_to_u64x2(t); | |
Self( | |
0xfffffffffff & t0, | |
0xfffffffffff & ((t0 >> 44) | (t1 << 20)), | |
0x3ffffffffff & (t1 >> 24), | |
) | |
} | |
#[inline] | |
fn from_u128_clamped(t: u128) -> Self { | |
let (t0, t1) = u128_to_u64x2(t); | |
Self( | |
0xffc0fffffff & t0, | |
0xfffffc0ffff & ((t0 >> 44) | (t1 << 20)), | |
0x00ffffffc0f & (t1 >> 24), | |
) | |
} | |
// New method to format as hex string including the high bit | |
fn to_hex_string(&self) -> String { | |
let high_bits = (self.2 >> 40) & 0b11; | |
let s = if high_bits != 0 { | |
format!("{:1x}{:032x}", high_bits, self.to_u128()) | |
} else { | |
format!("{:032x}", self.to_u128()) | |
}; | |
let t = s.trim_start_matches('0').to_string(); | |
if t.len() == 0 { | |
"00".to_string() | |
} else { | |
t | |
} | |
} | |
#[inline] | |
fn to_u128(&self) -> u128 { | |
(self.0 as u128) | ((self.1 as u128) << 44) | ((self.2 as u128) << 88) | |
} | |
#[inline] | |
fn add(&self, other: Self) -> Self { | |
Self(self.0 + other.0, self.1 + other.1, self.2 + other.2) | |
} | |
fn reduce(&self) -> Self { | |
// fully carry h | |
let mut h0 = self.0; | |
let mut h1 = self.1; | |
let mut h2 = self.2; | |
let mut c: u64 = h1 >> 44; | |
h1 &= 0xfffffffffff; | |
h2 += c; | |
c = h2 >> 42; | |
h2 &= 0x3ffffffffff; | |
h0 += c * 5; | |
c = h0 >> 44; | |
h0 &= 0xfffffffffff; | |
h1 += c; | |
c = h1 >> 44; | |
h1 &= 0xfffffffffff; | |
h2 += c; | |
c = h2 >> 42; | |
h2 &= 0x3ffffffffff; | |
h0 += c * 5; | |
c = h0 >> 44; | |
h0 &= 0xfffffffffff; | |
h1 += c; | |
// compute h + -p | |
let mut g0 = h0 + 5; | |
c = g0 >> 44; | |
g0 &= 0xfffffffffff; | |
let mut g1 = h1 + c; | |
c = g1 >> 44; | |
g1 &= 0xfffffffffff; | |
let mut g2 = h2.wrapping_add(c).wrapping_sub(1u64 << 42); | |
// select h if h < p, or h + -p if h >= p | |
c = (g2 >> ((8 * 8) - 1)).wrapping_sub(1); | |
g0 &= c; | |
g1 &= c; | |
g2 &= c; | |
c = !c; // in C, it was ~c | |
h0 = (h0 & c) | g0; | |
h1 = (h1 & c) | g1; | |
h2 = (h2 & c) | g2; | |
Self(h0, h1, h2) | |
} | |
fn mul(&self, r: Self) -> Self { | |
// Precompute s1 = r1 * 5 << 2 and s2 = r2 * 5 << 2 | |
let s1 = r.1 * (5 << 2); | |
let s2 = r.2 * (5 << 2); | |
let mut d0 = (self.0 as u128) * (r.0 as u128); | |
d0 = d0.wrapping_add((self.1 as u128) * (s2 as u128)); | |
d0 = d0.wrapping_add((self.2 as u128) * (s1 as u128)); | |
let mut d1 = (self.0 as u128) * (r.1 as u128); | |
d1 = d1.wrapping_add((self.1 as u128) * (r.0 as u128)); | |
d1 = d1.wrapping_add((self.2 as u128) * (s2 as u128)); | |
let mut d2 = (self.0 as u128) * (r.2 as u128); | |
d2 = d2.wrapping_add((self.1 as u128) * (r.1 as u128)); | |
d2 = d2.wrapping_add((self.2 as u128) * (r.0 as u128)); | |
// Partial reduction | |
let mut h0: u64; | |
let mut h1: u64; | |
let h2: u64; | |
let c = (d0 >> 44) as u64; | |
h0 = (d0 as u64) & 0xfffffffffff; | |
d1 = d1.wrapping_add(c as u128); | |
let c = (d1 >> 44) as u64; | |
h1 = (d1 as u64) & 0xfffffffffff; | |
d2 = d2.wrapping_add(c as u128); | |
let c = (d2 >> 42) as u64; | |
h2 = (d2 as u64) & 0x3ffffffffff; | |
h0 = h0.wrapping_add(c * 5); | |
let c = h0 >> 44; | |
h0 &= 0xfffffffffff; | |
h1 = h1.wrapping_add(c); | |
Self(h0, h1, h2) | |
} | |
} | |
// Format bytes as colon-separated hex, e.g. "01:03:80:8a" | |
fn bytes_to_colon_hex(bytes: &[u8]) -> String { | |
let mut hex = String::new(); | |
for (i, byte) in bytes.iter().enumerate() { | |
if i > 0 { | |
hex.push_str(":"); | |
} | |
hex.push_str(&format!("{:02x}", byte)); | |
} | |
hex | |
} | |
fn format_with_prefix(prefix: &str, bytes: &[u8], chars_per_line: usize, indent: usize) -> String { | |
let mut result = String::new(); | |
result.push_str(prefix); | |
let mut current_line_pos = prefix.len(); | |
for ch in bytes_to_colon_hex(bytes).chars() { | |
if current_line_pos >= chars_per_line { | |
result.push('\n'); | |
result.push_str(&" ".repeat(indent)); | |
current_line_pos = indent; | |
} | |
result.push(ch); | |
current_line_pos += 1; | |
} | |
result | |
} | |
fn hex_dump(data: &[u8]) { | |
const BYTES_PER_LINE: usize = 16; | |
let mut offset = 0; | |
while offset < data.len() { | |
// Print the offset | |
print!(" {:03} ", offset); | |
// Print the hex values | |
for i in 0..BYTES_PER_LINE { | |
if offset + i < data.len() { | |
print!("{:02x} ", data[offset + i]); | |
} else { | |
print!(" "); | |
} | |
} | |
// Print the ASCII representation | |
print!(" "); | |
for i in 0..BYTES_PER_LINE { | |
if offset + i < data.len() { | |
let byte = data[offset + i]; | |
// Only print printable ASCII characters (32-126), replace others with a dot | |
if byte >= 32 && byte <= 126 { | |
print!("{}", byte as char); | |
} else { | |
print!("."); | |
} | |
} else { | |
break; | |
} | |
} | |
println!(); | |
offset += BYTES_PER_LINE; | |
} | |
} | |
fn poly1305_testvectors<Field: P1305Field>() { | |
println!(); | |
println!("2.5.2. Poly1305 Example and Test Vector"); | |
println!(); | |
println!(" For our example, we will dispense with generating the one-time key"); | |
println!(" using AES, and assume that we got the following keying material:"); | |
println!(); | |
println!( | |
"{}", | |
format_with_prefix(" o Key Material: ", &DEFAULT_KEY_MATERIAL, 72, 6) | |
); | |
let s_bytes: [u8; 16] = DEFAULT_KEY_MATERIAL[16..32].try_into().unwrap(); | |
println!(); | |
println!(" o s as an octet string:"); | |
println!("{}", format_with_prefix(" ", &s_bytes, 72, 6)); | |
println!(); | |
println!(); | |
println!("Nir & Langley Informational [Page 15]"); | |
print!("\x0C"); | |
println!("RFC 7539 ChaCha20 & Poly1305 May 2015"); | |
println!(); | |
println!(); | |
let s_u128 = u128::from_le_bytes(s_bytes); | |
println!(" o s as a 128-bit number: {s_u128:016x}"); | |
println!(); | |
let r_bytes: [u8; 16] = DEFAULT_KEY_MATERIAL[0..16].try_into().unwrap(); | |
let r_u128 = u128::from_le_bytes(r_bytes); | |
let r = Field::from_u128_clamped(r_u128); | |
println!(" o r before clamping: {}", bytes_to_colon_hex(&r_bytes)); | |
println!(); | |
println!(" o Clamped r as a number: {:x}", r.to_u128()); | |
let message = "Cryptographic Forum Research Group".as_bytes(); | |
println!(); | |
println!(" For our message, we'll use a short text:"); | |
println!(); | |
println!(" Message to be Authenticated:"); | |
hex_dump(message); | |
println!(); | |
println!(" Since Poly1305 works in 16-byte chunks, the 34-byte message divides"); | |
println!(" into three blocks. In the following calculation, \"Acc\" denotes the"); | |
println!(" accumulator and \"Block\" the curren"); | |
println!(); | |
println!(" Block #1"); | |
println!(); | |
let acc = Field::zero(); | |
println!(" Acc = {}", acc.to_hex_string()); | |
let block_bytes: [u8; 16] = message[0..16].try_into().unwrap(); | |
let block_u128 = u128::from_le_bytes(block_bytes); | |
let block_naked = Field::from_u128(block_u128); | |
let block = block_naked.mark(); | |
println!(" Block = {}", block_naked.to_hex_string()); | |
println!(" Block with 0x01 byte = {}", block.to_hex_string()); | |
let acc_plus_block = acc.add(block); | |
println!(" Acc + block = {}", acc_plus_block.to_hex_string()); | |
let apb_mul_r = acc_plus_block.mul(r); | |
println!(" (Acc+Block) * r ="); | |
println!(" {}", apb_mul_r.to_hex_string()); | |
let modp = apb_mul_r.reduce(); | |
println!(" Acc = ((Acc+Block)*r) % P = {}", modp.to_hex_string()); | |
let acc = modp; | |
println!(); | |
println!(" Block #2"); | |
println!(); | |
println!(" Acc = {}", acc.to_hex_string()); | |
let block_bytes: [u8; 16] = message[16..32].try_into().unwrap(); | |
let block_u128 = u128::from_le_bytes(block_bytes); | |
let block_naked = Field::from_u128(block_u128); | |
let block = block_naked.mark(); | |
println!(" Block = {}", block_naked.to_hex_string()); | |
println!(" Block with 0x01 byte = {}", block.to_hex_string()); | |
let acc_plus_block = acc.add(block); | |
println!(" Acc + block = {}", acc_plus_block.to_hex_string()); | |
let apb_mul_r = acc_plus_block.mul(r); | |
println!(" (Acc+Block) * r ="); | |
println!(" {}", apb_mul_r.to_hex_string()); | |
let modp = apb_mul_r.reduce(); | |
println!(" Acc = ((Acc+Block)*r) % P = {}", modp.to_hex_string()); | |
let acc = modp; | |
println!(); | |
println!(" Last Block"); | |
println!(); | |
println!(" Acc = {}", acc.to_hex_string()); | |
let mut block_bytes = [0u8; 16]; | |
block_bytes[0] = message[32]; | |
block_bytes[1] = message[33]; | |
block_bytes[2] = 1; | |
let block_u128 = u128::from_le_bytes(block_bytes); | |
let block_naked = Field::from_u128(block_u128); | |
let block = block_naked; | |
println!(" Block = {}", block_naked.to_hex_string()); | |
println!(" Block with 0x01 byte = {}", block.to_hex_string()); | |
let acc_plus_block = acc.add(block); | |
println!(" Acc + block = {}", acc_plus_block.to_hex_string()); | |
let apb_mul_r = acc_plus_block.mul(r); | |
println!(" (Acc+Block) * r ="); | |
println!(" {}", apb_mul_r.to_hex_string()); | |
let modp = apb_mul_r.reduce(); | |
println!(" Acc = ((Acc+Block)*r) % P = {}", modp.to_hex_string()); | |
println!(); | |
println!(); | |
println!("Nir & Langley Informational [Page 16]"); | |
print!("\x0C"); | |
println!("RFC 7539 ChaCha20 & Poly1305 May 2015"); | |
println!(); | |
println!(); | |
println!(" Adding s, we get this number, and serialize if to get the tag:"); | |
println!(); | |
let acc_plus_s = modp.add(Field::from_u128(s_u128)); | |
println!(" Acc + s = {}", acc_plus_s.to_hex_string()); | |
println!(); | |
println!( | |
" Tag = {}", | |
bytes_to_colon_hex(&acc_plus_s.to_u128().to_le_bytes()) | |
); | |
println!(); | |
} | |
fn self_test() -> bool { | |
let mut p = Poly1305::<P1305u64>::new(&DEFAULT_KEY_MATERIAL); | |
p.update("Cryptographic Forum Research Group".as_bytes()); | |
let t = u128::from_le_bytes(p.finalize()); | |
return t == 224842052152609318683470184328606844584u128; | |
} | |
fn main() { | |
let args: Vec<String> = std::env::args().skip(1).collect(); | |
if args.is_empty() { | |
poly1305_testvectors::<P1305u64>(); | |
} | |
if !self_test() { | |
eprintln!("Error: self-test failed!"); | |
return; | |
} | |
if args.is_empty() { | |
println!("Usage: poly1305 <data1> [data2] [data3] ..."); | |
return; | |
} | |
let mut poly = Poly1305::<P1305u64>::new(&DEFAULT_KEY_MATERIAL); | |
for arg in args { | |
let bytes = arg.as_bytes(); | |
poly.update(bytes); | |
} | |
let tag = u128::from_le_bytes(poly.finalize()); | |
println!("{:016x}", tag); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment