-rw-r--r-- 2193 cryptattacktester-20230614/collision_prob.cpp raw
#include "queue_prob.h"
#include "collision_prob.h"
using namespace std;
template <typename big>
bigfloat generic_collision_average(big X,big Y,bigint r,bigfloat p)
{
vector<bigfloat> phiX = queue_distribution(X,p,r);
vector<bigfloat> phiY = queue_distribution(Y,p,r);
bigfloat S = 0;
bigfloat T = 0;
for (bigint j = 0;j < r;++j) S += phiX.at(j);
for (bigint j = 0;j < r;++j) T += phiY.at(j);
S = 1-S;
T = 1-T;
bigfloat result = 0;
result += (r*(r+1)/2)*S*T;
for (bigint e = 1;e < r;++e)
result += phiX.at(e)*(e*(e+1)/2+e*(r-e))*T;
for (bigint f = 1;f < r;++f)
result += phiY.at(f)*(f*(f+1)/2+f*(r-f))*S;
for (bigint e = 1;e < r;++e)
for (bigint f = 1;f < r;++f)
if (e+f < r)
result += phiX.at(e)*phiY.at(f)*e*f;
else
result += phiX.at(e)*phiY.at(f)*(e*f-(e+f-r)*(e+f-r-1)/2);
return result/p;
}
bigfloat collision_average(bigint X,bigint Y,bigint r,bigfloat p)
{
return generic_collision_average<bigint>(X,Y,r,p);
}
bigfloat collision_average(bigfloat X,bigfloat Y,bigint r,bigfloat p)
{
return generic_collision_average<bigfloat>(X,Y,r,p);
}
bigfloat collision_lastmatch_prob(bigfloat numsuccesses,bigfloat numinputs,bigfloat numoutputs)
{
// attack sees numsuccesses of the inputs
// golden input is found with probability numsuccesses/inputs
// but maybe other inputs are also found mapping to the same output
// and maybe attack finds one of those instead: bad collision
// model input-output mapping as uniform random
// for each j between 1 and numsuccesses:
// 1/numinputs chance that golden input is at position j
// have numsuccesses-j inputs that could get in the way
// each getting in the way with probability 1/numoutputs
// so avoid bad collision with probability (1-1/numoutputs)^(numsuccesses-j)
// total across j: ((1-1/numoutputs)^(numsuccesses-1)+...+(1-1/numoutputs)^1+(1-1/numoutputs)^0)/numinputs
// i.e. (1-(1-1/numoutputs)^numsuccesses)*numoutputs/numinputs
bigfloat x = log1p(-1/numoutputs); // log(1-1/numoutputs)
x *= numsuccesses; // numsuccesses*log(1-1/numoutputs)
x = -expm1(x); // 1-(1-1/numoutputs)^numsuccesses
return x*numoutputs/numinputs;
}