123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 28 October 2022
- # https://github.com/trizen
- # A very simple hash function (most likely, not secure), using the binomial function to create the avalanche effect.
- # See also:
- # https://oeis.org/A014062
- # https://yewtu.be/watch?v=KqqOXndnvic
- # https://en.wikipedia.org/wiki/Avalanche_effect
- define (
- BLOCK_SIZE = 16, # in bytes
- MODULO = 2**128,
- )
- func process_block(str) {
- func f(bits) {
- bits.sum_kv {|k,v|
- binomial(k*k + v, k)
- } % MODULO
- }
- while (str.len < BLOCK_SIZE) {
- var arr = str.bytes.map{.inc}
- str += arr.sum
- str += arr.prod
- }
- var A = f(str.ascii2bits)
- var B = f(str.reverse.ascii2bits)
- mulmod(A, B, MODULO)
- }
- func prepare_result(num) {
- sprintf('%0*s', 2*BLOCK_SIZE, num % MODULO -> as_hex)
- }
- func binomial_hash_string(str) {
- prepare_result(str.encode_utf8.split(BLOCK_SIZE).map(process_block).sum)
- }
- func binomial_hash_file(filename) {
- var total = 0
- var fh = File(filename).open('<:raw') || return nil
- while (fh.read(\var block, BLOCK_SIZE)) {
- total += process_block(block)
- }
- prepare_result(total)
- }
- var tests = [
- '',
- "\0",
- 'a',
- 'b',
- 'ab',
- 'ba',
- 'abc',
- 'acb',
- 'message digest',
- 'abcdefghijklmnopqrstuvwxyz',
- 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789',
- '12345678901234567890123456789012345678901234567890123456789012345678901234567890',
- ]
- for msg in tests {
- var hash = binomial_hash_string(msg)
- say "#{hash} : #{msg.dump}"
- }
- printf("\nBinomial hash of this script: %s\n\n", binomial_hash_file(__FILE__))
- #
- ## Run some special tests
- #
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(50.chr).join),
- binomial_hash_string(BLOCK_SIZE.dec.of(50.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(16.chr).join),
- binomial_hash_string(BLOCK_SIZE.dec.of(8.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(16.chr).join),
- binomial_hash_string(BLOCK_SIZE.dec.of(16.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.dec.of(15.chr).join),
- binomial_hash_string(BLOCK_SIZE.dec.dec.of(15.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.inc.of(2.chr).join),
- binomial_hash_string(BLOCK_SIZE.inc.inc.of(2.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(15.chr).join),
- binomial_hash_string(BLOCK_SIZE.dec.of(15.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.dec.of(14.chr).join),
- binomial_hash_string(BLOCK_SIZE.dec.dec.of(14.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.inc.of(1.chr).join),
- binomial_hash_string(BLOCK_SIZE.inc.inc.of(1.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(126.chr).join),
- binomial_hash_string(BLOCK_SIZE.of(63.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(254.chr).join),
- binomial_hash_string(BLOCK_SIZE.of(191.chr).join)
- )
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.of(124.chr).join),
- binomial_hash_string(BLOCK_SIZE.of(62.chr).join)
- )
- assert_ne(
- binomial_hash_string("1"),
- binomial_hash_string("149"),
- )
- for n in (48..52) {
- assert_ne(
- binomial_hash_string(BLOCK_SIZE.inc.of(n.chr).join),
- binomial_hash_string(BLOCK_SIZE.inc.inc.of(n.chr).join),
- "Collision for n = #{n}"
- )
- }
- __END__
- 00000000000000000000000000000000 : ""
- fea891fdc54930fd39620fcc478299f0 : "\0"
- e1a06e532bba0bcf2ef6115e06f6e410 : "a"
- 004cac7e4dcb9c4129aa7748278626f2 : "b"
- 82eb8712eb98d42f187531a7eb3f32b2 : "ab"
- c8f774efd7bc079c0b749703106346c2 : "ba"
- 23c44e458e6e4b79109b9a0417499796 : "abc"
- 643c218207789c53e40d246912feb456 : "acb"
- d55aee8c85258c85ed4a866bf4891014 : "message digest"
- 82a9f92413c1b3cac57f28488d61836b : "abcdefghijklmnopqrstuvwxyz"
- c4c22251fd0388692867eefe8af04b99 : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
- bfcdbe7ba1ae8243902eee55226f3a0c : "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
|