Криптографический хэш-гольф

34

Этот конкурс окончен.

Из-за характера проблем задача полицейских становится намного легче, когда интерес к связанной проблеме грабителей уменьшился. Поэтому, хотя вы все еще можете публиковать хэш-функции, ваш ответ не будет принят или станет частью списка лидеров.

Эта задача заключается в поиске самой короткой реализации хеш-функции, которая устойчива к коллизиям , т. Е. Должно быть невозможно найти два разных сообщения с одинаковым хеш-кодом.

Как полицейский, вы пытаетесь изобрести и реализовать хеш-функцию, находя лучший компромисс между размером кода и устойчивостью к коллизиям. Используйте слишком много байтов, и другой полицейский обгонит вас!

Как грабитель, вы пытаетесь помешать попыткам полицейских, взломав их функции, доказав, что они непригодны. Это заставит их использовать больше байтов для усиления своих алгоритмов!

Вызов копов

задача

Реализуйте криптографическую хеш-функцию H: I -> O по вашему выбору, где I - множество всех неотрицательных целых чисел ниже 2 2 30, а O - множество всех неотрицательных целых чисел ниже 2 128 .

Вы можете реализовать H как фактическую функцию, которая принимает и возвращает одно целое число, строковое представление целого числа или массив целых чисел или полную программу, которая читает из STDIN и печатает в STDOUT в основаниях 10 или 16.

счет

  • H что он должен противостоять вызову грабителей, определенному ниже.

    Если грабитель побеждает ваше представление в первые 168 часов после публикации, оно считается взломанным .

  • Реализация H должна быть максимально короткой. Самая короткая непроверенная подача будет победителем соревнования полицейских.

Дополнительные правила

  • Если вы реализуете H как функцию, пожалуйста, предоставьте оболочку для выполнения функции из программы, которая ведет себя так, как описано выше.

  • Пожалуйста, предоставьте не менее трех тестовых векторов для вашей программы или оболочки (например, входные данные и их соответствующие выходные данные).

  • H может быть вашим новым дизайном (предпочтительным) или известным алгоритмом, если вы реализуете его самостоятельно. Запрещается использовать любые встроенные хэш-функции, функции сжатия, шифрования, PRNG и т. Д.

    Любая встроенная функция, обычно используемая для реализации функций хеширования (например, базовое преобразование), является честной игрой.

  • Вывод вашей программы или функции должен быть детерминированным.

  • Должен быть бесплатный (как в пиве) компилятор / интерпретатор, который можно запустить на платформе x86 или x64 или из веб-браузера.

  • Ваша программа или функция должна быть достаточно эффективной и должна хэшировать любое сообщение в I ниже 2 2 19 менее чем за секунду.

    Для крайних случаев решающее значение будет иметь (настенное) время, необходимое на моем компьютере (Intel Core i7-3770, 16 ГБ ОЗУ).

  • Учитывая природу этой проблемы, запрещено каким-либо образом изменять код вашего ответа, независимо от того, изменяет ли он вывод или нет.

    Если ваша заявка была взломана (или даже нет), вы можете опубликовать дополнительный ответ.

    Если ваш ответ неверен (например, он не соответствует спецификации ввода / вывода), удалите его.

пример

Python 2.7, 22 байта

def H(M):
 return M%17

обертка

print H(int(input()))

Вызов грабителей

задача

Трещина любой из полицейских Доводы, разместив следующее в грабителей нити : два сообщения M и N в I таким образом, что H (M) = H (N) и M ≠ N .

счет

  • Взлом каждого подчиненного полицейского приносит вам одно очко. Грабитель с наибольшим количеством очков побеждает.

    В случае ничьей побеждает грабитель, взломавший самую длинную отправку.

Дополнительные правила

  • Каждое подчинение полицейского может быть взломано только один раз.

  • Если представление полицейского основано на поведении, определяемом реализацией или неопределенном, вам нужно только найти трещину, которая работает (достоверно) на вашем компьютере.

  • Каждая трещина принадлежит отдельному ответу в ветке грабителей.

  • Публикация недопустимой попытки взлома запрещает взломать эту конкретную отправку в течение 30 минут.

  • Вы не можете взломать ваше собственное представление.

пример

Python 2.7, 22 байта пользователем8675309

1

а также

18

Leaderboard

Безопасные представления

  1. CJam, 21 байт от электронного бизнеса
  2. C ++, 148 байт, tucuxi
  3. C ++, 233 (?) Байта от Vi.

Не взломанные представления

Вы можете использовать этот фрагмент стека, чтобы получить список еще не взломанных ответов.

function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>

Деннис
источник
Если хеш-функция ошибочно возвращает числа больше 2 ^ 128-1, делает ли это недействительным представление или мы просто возьмем результат по модулю 2 ^ 128?
Мартин Эндер
@ MartinBüttner: Да, вы должны взять результат по модулю 2 ^ 128.
Деннис
1
@Scimonster Не соответствует требованиям (до 2 ^ 30 бит ввода, 128 бит вывода)
CodesInChaos
1
Разве полицейские и грабители обычно не идут другим путем?
haneefmubarak
2
Возможно, у нас могло бы быть правило, что представления должны включать в себя примеры хэшей, довольно неприятно запускать выбранный язык программирования отправителей, чтобы иметь результат для сравнения с взломанной реализацией.
аааааааааааа

Ответы:

6

CJam, 21 байт

1q3*{i+_E_#*^26_#)%}/

Принимает строку байтов в качестве входных данных.

В псевдокоде:

hash = 1
3 times:
    for i in input:
        hash = hash + i
        hash = hash xor hash * 14^14
        hash = hash mod (26^26 + 1)
output hash

Пример хэшей:

"" (пустая строка) -> 1
"Тест" -> 2607833638733409808360080023081587841
"Тест" -> 363640467424586895504738713637444713

Это может быть немного проще, выходной диапазон составляет всего чуть более 122 бит, усиление тройной итерации уже немного нарушено, так как каждый раз он делает одно и то же, так что ввод в первом хэше 1 итерация будет полным перерывом. Но это коротко, и не слишком весело быть слишком безопасным.

AAAAAAAAAAAA
источник
Есть ли сопутствующая версия C, как в другом посте CJam?
Ви.
@Vi. Нет, пока нет. Я никогда не баловался с Bigint в C, есть ли стандартная библиотека для этого?
аааааааааааа
GMP ?
Ви.
3
Здесь: pastebin.com/SDzA3JK4
брезгливый оссифраж
1
@ Agawa001 Вы перепутали свою терминологию. Это алгоритм хеш-функции тройного прохода. Шифр Цезаря - это один конкретный алгоритм шифрования без внутреннего состояния.
аааааааааааа
7

Python, 109 байт [ треснул , и снова ]

def f(n,h=42,m=2**128):
 while n:h+=n&~-m;n>>=128;h+=h<<10;h^=h>>6;h%=m
 h+=h<<3;h^=h>>11;h+=h<<15;return h%m

Я попытался реализовать единовременную функцию Дженкинса как есть, с единственной разницей, состоящей из начального числа и количества битов.

Забавный факт: очевидно, Perl в какой-то момент использовал хеш Дженкинса .

обертка

print(f(int(input())))

Примеры

>>> f(0)
12386682
>>> f(1)
13184902071
>>> f(2**128-1)
132946164914354994014709093274101144634
>>> f(2**128)
13002544814292
>>> f(2**128+1)
13337372262951
>>> f(2**(2**20))
290510273231835581372700072767153076167
Sp3000
источник
6

C ++, 148 байт

typedef __uint128_t U;U h(char*b,U n,U&o){U a=0x243f6a8885a308d,p=0x100000001b3;for(o=a;n--;)for(U i=27;--i;){o=(o<<i)|(o>>(128-i));o*=p;o^=b[n];}}

__uint128_t является расширением GCC и работает как положено. Хеш основан на итерации хеша FNV (я позаимствовал их простое число, хотя aэто первые цифры числа Pi в шестнадцатеричном формате) с поворотом, подобным sha1, в начале каждой итерации. Компиляция с использованием -O3хэширования файла размером 10 МБ занимает менее 2 секунд, поэтому все еще есть запас для увеличения числа итераций во внутреннем цикле, но сегодня я чувствую себя щедрым.

Отключите (изменили имена переменных, добавили комментарии, пробелы и пару скобок) для вашего удовольствия от взлома:

typedef __uint128_t U;
U h(char* input, U inputLength, U &output){
    U a=0x243f6a8885a308d,p=0x100000001b3;    
    for(output=a;inputLength--;) {   // initialize output, consume input
        for(U i=27;--i;) {                          // evil inner loop
            output = (output<<i)|(output>>(128-i)); // variable roll 
            output *= p;                            // FNV hash steps
            output ^= input[inputLength];        
        }
    }
    // computed hash now available in output
}

Предложения по игре в гольф приветствуются (даже если я не смогу улучшить код на их основе).

редактировать: исправлены опечатки в деуглифицированном коде (версия для гольфа остается неизменной).

белый дельфин
источник
oкажется неинициализированным. Где outputзаявлено? Или , может быть , oэто output?
Ви.
То же самое для n. Вы действительно проверили «деуглифицированный» код для запуска?
Ви.
Запустил брутфорсер ...
Ви.
Даже 3-х раундовая версия нелегка.
Ви.
@Vi. Исправлена ​​деуглифицированная версия - извините за то, что не проверил ее лучше. Я горжусь этой внутренней петлей; U i=81;i-=3мог бы быть еще более мерзким, без значительных затрат времени выполнения.
Tucuxi
5

CJam, 44 байт [ трещина ]

lW%600/_z]{JfbDbGK#%GC#[md\]}%z~Bb4G#%\+GC#b

Вход в базу 10.

CJam медленный. Я надеюсь, что это работает в 1 секунду на каком-то компьютере ...

Пояснения

lW%600/            e# Reverse, and split into chunks with size 600.
_z                 e# Duplicate and swap the two dimensions.
]{                 e# For both versions or the array:
    JfbDb          e# Sum of S[i][j]*13^i*19^j, where S is the character values,
                   e# and the indices are from right to left, starting at 0.
    GK#%GC#[md\]   e# Get the last 32+48 bits.
}%
z~                 e# Say the results are A, B, C, D, where A and C are 32 bits.
Bb4G#%             e# E = the last 32 bits of A * 11 + C.
\+GC#b             e# Output E, B, D concatenated in binary.

Что ж, двумерные вещи казались слабостью ... Вначале предполагалось ускорить некоторые медленные вычисления. Но он не может работать за секунду, независимо от того, что я делаю, поэтому я наконец удалил медленный код.

Также должно быть лучше, если бы я использовал двоичные биты и старшие основания.

C версия

__uint128_t hash(unsigned char* s){
    __uint128_t a=0,b=0;
    __uint128_t ar=0;
    __uint128_t v[600];
    int l=0,j=strlen(s);
    memset(v,0,sizeof v);
    for(int i=0;i<j;i++){
        if(i%600)
            ar*=19;
        else{
            a=(a+ar)*13;
            ar=0;
        }
        if(i%600>l)
            l=i%600;
        v[i%600]=v[i%600]*19+s[j-i-1];
        ar+=s[j-i-1];
    }
    for(int i=0;i<=l;i++)
        b=b*13+v[i];
    a+=ar;
    return (((a>>48)*11+(b>>48))<<96)
        +((a&0xffffffffffffull)<<48)
        +(b&0xffffffffffffull);
}
jimmy23013
источник
Не могли бы вы добавить описание? Не все знают CJam.
orlp
@orlp Отредактировано ...
jimmy23013
На моем компьютере это занимает 0,4 с, поэтому оно находится в допустимых пределах.
Деннис
Что такое А, В, С и так далее? Некоторые матрицы? Какие размеры? Может ли это быть легко реализовано в C?
Ви.
1
Трещины , я считаю.
Sp3000
5

C ++, 182 символа (+ около 51 символа стандартного образца)

h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=buf[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}

Шаблонный:

void hash(const unsigned char* buf, size_t len, unsigned long long *hash1, unsigned long long *hash2)
{
    unsigned long long &h=*hash1;
    unsigned long long &j=*hash2;
    size_t l = len;
    const unsigned char* b = buf;

    // code here
}

Запускаемая программа с функцией гольфа

#include <stdio.h>

// The next line is 227 characters long
int hash(char*b,int l,long long&h,long long&j){h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=b[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}}

int main() {
    char buf[1024];
    int l  = fread(buf, 1, 1024, stdin);
    long long q, w;
    hash(buf, l, q, w);
    printf("%016llX%016llX\n", q, w);
}
Vi.
источник
2
Я думаю, что объявление функции и т. Д. Засчитывается в счетчик символов.
Ypnypn
@Ypnypn, подсчитанные символы в объявлении функции в гольфе.
Ви.
Что такое выходной хеш? Я предполагаю, что это ((h << 64) | j).
Tucuxi
Да. Или просто пара 64-битных чисел. Я узнал об этом __uint128_tтолько после реализации этого.
Ви.
1
@ Денис, Готово.
Ви.
4

Pyth, 8 трещины

sv_`.lhQ

Попробуйте онлайн

Немного глупый ответ, я объясню, как это работает, потому что большинство людей не умеют читать Pyth. Это берет натуральный логарифм одного плюс вход, и затем преобразовывает это в строку. Эта строка переворачивается, а затем оценивается и затем преобразуется в целое число.

Перевод Python будет выглядеть так:

import math
n = eval(input()) + 1
rev = str(math.log(n))[::-1]
print(int(eval(rev)))
FryAmTheEggman
источник
Трещины ?
Sp3000
4

Python 3, 216 байт [ взломан ]

def f(m):
 h=1;p=[2]+[n for n in range(2,102)if 2**n%n==2];l=len(bin(m))-2;*b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])
 while b:
  h*=h
  for P in p:
   if b:h=h*P**b.pop()%0xb6ee45a9012d1718f626305a971e6a21
 return h

Из-за несовместимости со спецификацией я могу вспомнить хотя бы одну небольшую уязвимость, но кроме этого я думаю, что это как минимум доказательство грубой силы. Я проверил первые 10 миллионов хэшей, между прочим.

С точки зрения гольфа это было бы короче в Python 2, но я пожертвовал некоторыми байтами ради эффективности (так как в любом случае это, вероятно, не победит).

Редактировать: это была моя попытка реализовать Very Smooth Hash , но, к сожалению, 128-бит был слишком мал.

обертка

print(f(int(input())))

Примеры

>>> f(0)
2
>>> f(123456789)
228513724611896947508835241717884330242
>>> f(2**(2**19)-1)
186113086034861070379984115740337348649
>>> f(2**(2**19))
1336078

Объяснение кода

def f(m):
 h=1                                             # Start hash at 1
 p=[2]+[n for n in range(2,102)if 2**n%n==2]     # p = primes from 2 to 101
 l=len(bin(m))-2                                 # l = bit-length of m (input)
 *b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])      # Convert bits to list, padding to
                                                 # a multiple of 26 then adding the
                                                 # bit-length at the front

 while b:                                        # For each round
  h*=h                                           # Square the hash
  for P in p:                                    # For each prime in 2 ... 101
   if b:h=(h*P**b.pop()                          # Multiply by prime^bit, popping
                                                 # the bit from the back of the list
           %0xb6ee45a9012d1718f626305a971e6a21)  # Take mod large number

 return h                                        # Return hash

Пример заполнения для f(6):

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

(len 3)(------------------ 23 zeroes for padding -------------------------)(input 6)
       (---------------------------- length 26 total ------------------------------)
Sp3000
источник
Cracked
feersum
4

C, 87 байт [ взломано ]

Это полная программа; Обертка не требуется. Принимает двоичный ввод через стандартный ввод и выводит шестнадцатеричный хеш в стандартный вывод.

c;p;q;main(){while((c=getchar())+1)p=p*'foo+'+q+c,q=q*'bar/'+p;printf("%08x%08x",p,q);}

Это только вычисляет 64-битный хеш, поэтому я немного рискну здесь.

В случае, если кому-то интересно, две константы 'foo+'и 'bar/'являются простыми числами 1718578987 и 1650553391.


Примеры:

Игнорирует ведущие нули:

echo -ne '\x00\x00\x00\x00' |./hash
0000000000000000

Однобайтовые входы:

echo -ne '\x01' |./hash
0000000100000001
echo -ne '\xff' |./hash
000000ff000000ff

Многобайтовые входы:

echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15c
echo -ne 'Hello, World' |./hash
04f1a7412b17b86c
брезгливый оссифраж
источник
Как бы он себя с «aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa» и «aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa»?
Исмаэль Мигель
1
foo|(d5c9bef71d4f5d1b) и foo\(d5c9bef71d4f5d1b) создают ОЧЕНЬ похожие хэши.
Исмаэль Мигель
1
Сломал это !!! \x00и \x00\x00!
Исмаэль Мигель
1
Основываясь на комментариях чата, я считаю, что это еще не взломан еще? Просто двойная проверка, потому что комментарий с голосованием может сбить с толку тех, кто просматривает хэши без взлома.
Sp3000
3

J - 39 байт - взломан

Функция, принимающая строку в качестве входных данных и возвращающая целое число <2 128 . Я предполагаю, что мы должны назвать нашу функцию допустимой, поэтому удалите еще 3 символа из числа, если мы можем представить анонимные функции.

H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]

Для тех из вас, кто не читает иероглифы, вот краткое изложение того, что я делаю.

  • a=.(2^128x)&|@^/@Это подпрограмма *, которая принимает массив чисел, а затем обрабатывает его как энергетическую вышку, где возведение в степень берется в мод 2 128 . Под «башней власти» я имею в виду, что если вы дадите ей ввод 3 4 5 6, она рассчитает 3 ^ (4 ^ (5 ^ 6)).
  • (".p:@+5,9:)aЭта функция берет строку, преобразует ее в число N , а затем вычисляет ( n +5) -ое и ( n +9) -ое простое число, а затем выбрасывает в aнее значение before. То есть мы находим p(n+5) ^ p(n+9)мод 2 128, где p(k)находится k-ое простое число.
  • H=:_8...\(a...)]Выполните описанную выше функцию для 8-символьных субблоков ввода, а затем соберите aвсе результаты вместе и вызовите результирующую хеш-функцию H. Я использую 8 символов, потому что kфункция " -th prime" J не работает, когда p(k)> 2 31 , т.е. k=105097564это самый большой сейф k.

Есть некоторые примеры выходных данных. Вы можете попробовать это самостоятельно на сайте tryj.tk , но я действительно рекомендую делать это дома, загрузив переводчик с Jsoftware .

   H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]
   H '88'
278718804776827770823441490977679256075
   H '0'
201538126434611150798503956371773
   H '1'
139288917338851014461418017489467720433
   H '2'
286827977638262502014244740270529967555
   H '3'
295470173585320512295453937212042446551
   30$'0123456789'  NB. a 30 character string
012345678901234567890123456789
   H 30$'0123456789'
75387099856019963684383893584499026337
   H 80$'0123456789'
268423413606061336240992836334135810465

* Технически, это не функция сама по себе, она присоединяется к другим функциям и влияет на их вывод. Но это семантическая проблема J, а не концептуальное различие: поток программы такой, как я описал выше.

algorithmshark
источник
2

Python 3, 118 байт [ взломан ]

def H(I):
    o=0;n=3;M=1<<128
    for c in I:i=ord(c);o=(o<<i^o^i^n^0x9bb90058bcf52d3276a7bf07bcb279b7)%M;n=n*n%M
    return o

Отступ - это одна вкладка. Простой хэш, еще не проверил его полностью.

Звоните следующим образом:

print(H("123456789"))

результат: 73117705077050518159191803746489514685

tomsmeding
источник
Как следует преобразовать входное целое число в строку для использования в вашем алгоритме?
feersum
Строка @feersum base-10 - это то, что я тестировал. Он ничего не использует, но ord(c), на самом деле, подойдет любая строка :) (кроме таких вещей, как nul chars, я думаю, что это делает коллизию хешей действительно легкой. Так что придерживайтесь строки 0-9.)
tomsmeding
1
Сломал его: codegolf.stackexchange.com/a/51160/41288 . Начнем с наблюдения, что строки типа "10000" и "20000" производят очень близкие хэши. Начал играть все больше и больше нулей, и после 128 или около того любая цифра + k * 4 повторения нуля возвращает один и тот же хеш независимо от k.
Tucuxi
@tucuxi Уже думал, что это не должно быть слишком сложно; рад, что это не тривиально, но кто-то сломал это все равно. Хорошая работа.
Томсминг
2

C ++, 239 байт

Мой самый первый кодовый гольф! [ Пожалуйста, будьте нежны ]

#define r(a,b) ((a<<b)|(a>>(64-b)))
typedef uint64_t I;I f(I*q, I n, I&h){h=0;for(I i=n;--i;)h=r(h^(r(q[i]*0x87c37b91114253d5,31)*0x4cf5ad432745937f),31)*5+0x52dce729;h^=(h>>33)*0xff51afd7ed558ccd;h^=(h>>33)*0xc4ceb9fe1a85ec53;h^=(h>>33);}

Безголовая версия:

I f(I* q, I n, I& h) // input, length and output
{
    h = 0; // initialize hashes
    for (I i=n;--i;)
    {
        q[i] *= 0x87c37b91114253d5;
        q[i]  = rotl(q[i], 31);
        q[i] *= 0x4cf5ad432745937f;

        h ^= q[i]; // merge the block with hash

        h *= rotl(h, 31);
        h = h * 5 + 0x52dce729;
    }
    h ^= h>>33;
    h *= 0xff51afd7ed558ccd;
    h ^= h>>33;
    h *= 0xc4ceb9fe1a85ec53; // avalanche!
    h ^= h>>33;
}

Не самый лучший хэш и определенно не самый короткий код из существующих. Принимать советы по гольфу и надеяться на улучшение!

обертка

Вероятно, не самый лучший в мире, но, тем не менее, обертка

I input[500];

int main()
{
    string s;
    getline(cin, s);
    memcpy(input, s.c_str(), s.length());
    I output;
    f(input, 500, output);
    cout << hex << output << endl;
}
SpelingMistake
источник
2
Выглядит солидно, но с 64 битами он может быть подвергнут грубому принуждению. Вероятность нахождения коллизии в тестах ~ sqrt (n) составляет около 50% (из общего числа n результатов); 2 ^ 32 попытки это не так уж много для современного компьютера.
Tucuxi
Оболочке не хватает заголовочных включений, и в общем случае получается много одинаковых хэшей.
Ви.
Предоставьте несколько образцов хеша. Для меня и «3», и «33» ведут к 481c27f26cba06cf (используя эту обертку).
Ви.
Взломан : codegolf.stackexchange.com/a/51215/41288 . Я подозреваю прямо перед @Vi. выяснил, почему так много хэшей были равны.
Tucuxi
1
Правильное столкновение (без использования ошибки): printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_-> a4baea17243177fd; printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_-> a4baea17243177fd. Bruteforcer находит здесь коллизии гораздо быстрее, чем в других 64-битных хэшах.
Ви.
2

Java, 299 291 282 байта, взломан.

import java.math.*;class H{public static void main(String[]a){BigInteger i=new java.util.Scanner(System.in).nextBigInteger();System.out.print(BigInteger.valueOf(i.bitCount()*i.bitLength()+1).add(i.mod(BigInteger.valueOf(Long.MAX_VALUE))).modPow(i,BigInteger.valueOf(2).pow(128)));}}

Выполняет некоторые операции с BigIntegers, затем принимает результат по модулю 2 128 .

SuperJedi224
источник
Как мне это запустить? Ideone отказывается его компилировать.
Мартин Эндер
1
Вы можете запустить его на Ideone, переименовав класс в «Main» или удалив первое «public» ключевое слово (но НЕ второе). Либо один будет работать.
SuperJedi224
Трещины.
Мартин Эндер
1
@ SuperJedi224 Почему бы не удалить первый publicсамостоятельно, сохранив 7 символов?
user253751
@immibis Потому что тогда я не думаю, что это сработает правильно на Eclipse. Я попробую это все же. РЕДАКТИРОВАТЬ: Я думаю, что это так. Это сюрприз.
SuperJedi224
2

C, 128 байт [ взломано ]

p;q;r;s;main(c){while((c=getchar())+1)p=p*'foo+'+s^c,q=q*'bar/'+p,r=r*'qux3'^q,s=s*'zipO'+p;printf("%08x%08x%08x%08x",p,q,r,s);}

Это более или менее тот же алгоритм, что и в моей последней попытке (взломанный Vi.) , Но теперь у него достаточно колес хомяка для генерации правильных 128-битных хэшей.

Четыре простых константы в коде следующие:

'foo+' = 1718578987
'bar/' = 1650553391
'qux3' = 1903523891
'zipO' = 2053730383

Как и прежде, это полная программа без необходимости в обертке. Целое число I вводится через stdin как необработанные двоичные данные (big-endian), а хэш O выводится в шестнадцатеричном виде в стандартный вывод. Ведущие нули в I игнорируются.

Примеры:

echo -ne '\x00' |./hash
00000000000000000000000000000000
echo -ne '\x00\x00' |./hash
00000000000000000000000000000000
echo -ne '\x01' |./hash
00000001000000010000000100000001
echo -ne 'A' |./hash
00000041000000410000004100000041
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15cb9a5996fe0d8df7c
echo -ne 'Hello, World' |./hash
da0ba2857116440a9bee5bb70d58cd6a
брезгливый оссифраж
источник
1
Трещины codegolf.stackexchange.com/a/51216/101
AAAAAAAAAAAA
Разве ваш пример не показал столкновение прямо там (первые два)?
mbomb007
@ mbomb007 Нет. Вводится число от 0 до 2 ^ (2 ^ 30). 0x00 и 0x0000 оба равны нулю, поэтому они дают одинаковый результат.
брезгливое оссифраж
2

C, 122 байта [ взломан ]

long long x,y,p;main(c){for(c=9;c|p%97;c=getchar()+1)for(++p;c--;)x=x*'[3QQ'+p,y^=x^=y^=c*x;printf("%016llx%016llx",x,y);}

Вложенные циклы, недоделанные LCG и переменная замена. Что не любить?

Вот отличная версия для игры:

long long x,y,p;

int main(int c){
    // Start with a small number of iterations to
    //   get the state hashes good and mixed because initializing takes space
    // Then, until we reach the end of input (EOF+1 == 0)
    //   and a position that's a multiple of 97
    for (c=9;c|p%97;c=getchar()+1) {

        // For each input c(haracter) ASCII value, iterate down to zero
        for (++p;c--;) {

            // x will act like a LCG with a prime multiple
            //   partially affected by the current input position
            // The string '[3QQ' is the prime number 0x5B335151
            x=x*'[3QQ'+p;

            // Mix the result of x with the decrementing character
            y^=c*x;

            // Swap the x and y buffers
            y^=x^=y;
        }
    }

    // Full 128-bit output
    printf("%016llx%016llx",x,y);
    return 0;
}

Это полностью автономная программа, которая читает из STDIN и печатает в STDOUT.

Пример:

> echo -n "Hello world" | ./golfhash
b3faef341f70c5ad6eed4c33e1b55ca7

> echo -n "" | ./golfhash
69c761806803f70154a7f816eb3835fb

> echo -n "a" | ./golfhash
5f0e7e5303cfcc5ecb644cddc90547ed

> echo -n "c" | ./golfhash
e64e173ed4415f7dae81aae0137c47e5

В некоторых простых тестах он хэширует около 3 МБ / с текстовых данных. Скорость хеширования зависит от самих входных данных, так что это, вероятно, следует учитывать.

Мистер лама
источник
1
Взломано
aaaaaaaaaaaa
1

PHP 4.1, 66 байт [ взломано ]

Я просто разогреваюсь.

Я надеюсь, вы найдете это интересным.

<?for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

Я пробовал номера размером до 999999999999999999999999999.
Выходные данные оказались в диапазоне 2 128 .


PHP 4.1 требуется из-за register_globalsдирективы.

Он работает путем автоматического создания локальных переменных из сеанса, POST, GET, REQUEST и файлов cookie.

Он использует ключ a. (Например, доступ более http://localhost/file.php?a=<number>).

Если вы хотите протестировать его с PHP 4.2 и новее, попробуйте это:

<?for($l=strlen($b.=$a=$_REQUEST['a']*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

Эта версия работает только с POST и GET.


Пример вывода:

0 -> 0000000000000000000000000000000000000000
9 -> 8111111111111111111111111111111111111111
9999 -> 8888111111111111111111111111111111111111
1234567890 -> 0325476981111111111111111111111111111111
99999999999999999999999999999999999999999999999999999999999999999999999999999999 -> 0111191111111111111111111111111111111111

(Уверяю вас, что есть числа, которые производят одинаковый хэш).

Исмаэль Мигель
источник
1

C, 134 байта, треснувший

Это полная C программа.

long long i=0,a=0,e=1,v,r;main(){for(;i++<323228500;r=(e?(scanf("%c",&v),e=v>'/'&&v<':',v):(a=(a+1)*7)*(7+r)));printf("0x%llx\n", r);}

Что он делает: Идея состоит в том, чтобы взять входные данные в виде массива байтов и добавить псевдослучайные (но детерминированные) байты в конце, чтобы сделать длину равной примерно 2 2 30 (немного больше). Реализация считывает входной байт за байтом и начинает использовать псевдослучайные данные, когда находит первый символ, который не является цифрой.

Поскольку встроенный PRNG не разрешен, я реализовал его сам.

Существует неопределенное / определяемое реализацией поведение, которое делает код короче (конечное значение должно быть без знака, и я должен использовать разные типы для разных значений). И я не мог использовать 128-битные значения в C. Менее запутанная версия:

long long i = 0, prand = 0, notEndOfInput = 1, in, hash;

main() {
    for (; i++ < 323228500;) {
        if (notEndOfInput) {
            scanf("%c", &in);
            notEndOfInput = in >= '0' && in <= '9';
            hash = in;
        } else {
            prand = (prand + 1)*7;
            hash = prand*(7 + hash);
        }
    }
    printf("0x%llx\n", hash);
}
barteks2x
источник
Треснувший
брезгливый оссифраж
1

Python 2.X - 139 байт [[ Cracked ]]

Это очень похоже на все другие хеши (LOOP, XOR, SHIFT, ADD) здесь. Приди и получи свои очки грабителей;) Я сделаю сложнее, когда этот будет решен.

M=2**128
def H(I):
 A=[1337,8917,14491,71917];O=M-I%M
 for z in range(73):
  O^=A[z%4]**(9+I%9);O>>=3;O+=9+I**(A[z%4]%A[O%4]);O%=M
 return O

Оболочка (ожидает один аргумент в base-16, также известный как шестнадцатеричный):

import sys
if __name__ == '__main__':
 print hex(H(long(sys.argv[1], 16)))[2:][:-1].upper()
недоуменный
источник
Взломано
математика
1
Кроме того, я не уверен, что эта запись соответствует спецификации OP, так как на моем компьютере функция занимает несколько секунд на больших входах. Например, H(2**(2**10))заняло около 8 или 9 секунд, в то время как H(2**(2**12))заняло около 29 секунд и H(2**(2**14))заняло более двух минут.
Матмандан
Вы абсолютно правы, я, очевидно, должен был проверить время для больших входов. Кроме того, я, кажется, забыл запустить свой собственный тест после добавления этой смены. Первоначальная версия была без сдвига (до публикации) и проходила мой тест «нет столкновений в первых 100000 целых числах»: /
озадачено
1

Python 2,7 - 161 байт [[ Cracked ]]

Ну, так как мне удалось изменить свою первую хэш-функцию в бесполезную версию перед публикацией, я думаю, что я опубликую другую версию аналогичной структуры. На этот раз я проверил его на предмет тривиальных столкновений и проверил большинство возможных входных величин для скорости.

A=2**128;B=[3,5,7,11,13,17,19]
def H(i):
 o=i/A
 for r in range(9+B[i%7]):
  v=B[i%7];i=(i+o)/2;o=o>>v|o<<128-v;o+=(9+o%6)**B[r%6];o^=i%(B[r%6]*v);o%=A
 return o

Оболочка (не учитывается в байтсчете)

import sys
if __name__ == '__main__':
 arg = long(sys.argv[1].strip(), 16)
 print hex(H(arg))[2:][:-1].upper()

Пример запуска (ввод всегда шестнадцатеричное число):

$ python crypt2.py 1
3984F42BC8371703DB8614A78581A167
$ python crypt2.py 10
589F1156882C1EA197597C9BF95B9D78
$ python crypt2.py 100
335920C70837FAF2905657F85CBC6FEA
$ python crypt2.py 1000
B2686CA7CAD9FC323ABF9BD695E8B013
$ python crypt2.py 1000AAAA
8B8959B3DB0906CE440CD44CC62B52DB
недоуменный
источник
1
Трещины .
jimmy23013
Молодец, Джимми :)
озадачен
1

Рубин, 90 байт

def H(s);i=823542;s.each_byte{|x|i=(i*(x+1)+s.length).to_s.reverse.to_i%(2**128)};i;end

Весьма случайный алгоритм хеширования, который я составил, не глядя ни на какие настоящие хэши ... не знаю, хорош ли он. он принимает строку в качестве ввода.

Упаковочный:

def buildString(i)
  if(i>255)
    buildString(i/256)+(i%256).chr
  else
    i.chr
  end
end 
puts H buildString gets
MegaTom
источник
Не могли бы вы предоставить упаковку, которую требует вопрос?
Деннис
Какой формат ввода? Я пытался с номером, но он говорит comparison of String with 255 failed (ArgumentError).
jimmy23013
H принимает строку, Build string принимает число, требуемое OP, и преобразует его в строку.
MegaTom
Я думаю, что вам нужно gets.to_iв обертке.
jimmy23013
Трещины .
jimmy23013
0

Mathematica, 89 байт, трещины

Last@CellularAutomaton[(a=Mod)[#^2,256],{#~IntegerDigits~2,0},{#~a~99,128}]~FromDigits~2&

Не самый короткий.

LegionMammal978
источник
3
Как вы управляете этим без Mathematica? «Должен быть бесплатный (как в пиве) компилятор / интерпретатор, который можно запустить на платформе x86 или x64 или из веб-браузера».
Мартин Эндер
2
@ MartinBüttner wolfram.com/mathematica/trial
LegionMammal978
Трещины.
Мартин Эндер
0

PHP, 79 байт (взломано. С комментарием):

echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);

Это делает много страшных вещей посредством преобразования типов в php, что затрудняет предсказание;) (или, по крайней мере, я на это надеюсь). Однако это не самый короткий или нечитаемый ответ.

Для его запуска вы можете использовать PHP4 и зарегистрировать глобальные переменные (с? I = 123) или использовать командную строку:

php -r "$i = 123.45; echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);"
Sebb
источник
5
Выходное значение хеша выглядит с плавающей точкой. И то же самое для 3000000000000000000000000000000000000000000001 и 3000000000000000000000000000000000000000000000000000000000.
Vi.
0

C # - 393 байта взломаны

using System;class P{static void Main(string[]a){int l=a[0].Length;l=l%8==0?l/8:l/8+1;var b=new byte[l][];for(int i=0;i<l;i++){b[i]=new byte[8];};int j=l-1,k=7;for(int i=0;i<a[0].Length;i++){b[j][k]=Convert.ToByte(""+a[0][i],16);k--;if((i+1)%8==0){j--;k=7;}}var c=0xcbf29ce484222325;for(int i=0;i<l;i++){for(int o=0;o<8;o++){c^=b[i][o];c*=0x100000001b3;}}Console.WriteLine(c.ToString("X"));}}

Ungolfed:

using System;
class P
{
    static void Main(string[]a)
    {
      int l = a[0].Length;
      l = l % 8 == 0 ? l / 8 : l / 8 + 1;
      var b = new byte[l][];
      for (int i = 0; i < l; i++) { b[i] = new byte[8]; };
      int j = l-1, k = 7;
      for (int i = 0; i < a[0].Length; i++)
      {
        b[j][k] = Convert.ToByte(""+a[0][i], 16);
        k--;
        if((i+1) % 8 == 0)
        {
          j--;
          k = 7;
        }
      }
      var c = 0xcbf29ce484222325;
      for (int i = 0; i < l; i++)
      {
        for (int o = 0; o < 8; o++)
        {
          c ^= b[i][o];
          c *= 0x100000001b3;
        }
      }
      Console.WriteLine(c.ToString("X"));
    }
}

Я никогда не касался криптографии или хэширования в своей жизни, так что будьте осторожны :)

Это простая реализация хеша FNV-1a с поворотом массива на входе. Я уверен, что есть лучший способ сделать это, но это лучшее, что я мог сделать.

Это может использовать немного памяти на длинных входах.

ldam
источник
Cracked: codegolf.stackexchange.com/a/51277/101 В дополнение к ошибочному заполнению, это не криптографический хеш, есть очень много способов его сломать.
аааааааааааа
0

Python 2, 115 байт [ уже взломано! ]

ОК, вот мои последние усилия. Всего 115 байтов, потому что последний перевод строки не требуется.

h,m,s=1,0,raw_input()
for c in[9+int(s[x:x+197])for x in range(0,len(s),197)]:h+=pow(c,257,99**99+52)
print h%4**64

Это полная программа, которая вводит десятичное целое число в стандартный вывод и печатает десятичное значение хеша в стандартный вывод. Дополнительные начальные нули приведут к различным значениям хеш-функции, поэтому я просто предполагаю, что входные данные не имеют никаких.

Это работает путем заполнения 197-значных кусков входного числа посредством модульного возведения в степень. В отличие от некоторых языков, по int()умолчанию функция всегда имеет базовое значение 10, int('077')равно как и 77, а не 63.

Пример выходов:

$ python hash.py <<<"0"
340076608891873865874583117084537586383

$ python hash.py <<<"1"
113151740989667135385395820806955292270

$ python hash.py <<<"2"
306634563913148482696255393435459032089

$ python hash.py <<<"42"
321865481646913829448911631298776772679

$ time python hash.py <<<`python <<<"print 2**(2**19)"`
233526113491758434358093601138224122227

real    0m0.890s   <-- (Close, but fast enough)
user    0m0.860s
sys     0m0.027s
брезгливый оссифраж
источник
1
Он не использовал порядок блоков ... Трещины .
jimmy23013
Тьфу. Я сдаюсь :-(
брезгливый ossifrage