# Tag Info

3

It may be possible to use the knapsack problem to build a secure cryptosystem, though experience suggests it is tricky and delicate. There are many known algorithms for attacking the knapsack problem, which may or may not work, depending upon the specific parameters you choose. Therefore, the security of the scheme will depend on the specific parameter ...

1

In the Naccache-Stern knapsack cryptosystem, it holds that $\gcd(s,p-1) = 1$. Hence, you can compute the inverse of $s$ modulo $p-1$ (the coprimality ensure the existence of such an inverse). Computing this inverse can be done with the extended Euclidean algorithm, which gives you $u,v$ such that $su + (p-1) v = 1$: as $su = 1 \bmod p-1$, $u$ is indeed the ...

1

Here's the idea: given $w$ and $n$, we find a number $v$ such that $vw \equiv 1 \pmod{n}$. In your case of $w=7$ and $n=173$, we have $v=99$; such a $v$ will always exist if $w$ and $n$ are relatively prime, and can be found by the extended Euclidean algorithm. The value $v$ allows us to map from the "hard values" to the "superincreasing ones". Here's how ...

1

No, the problem is np-completeness or even np-hardness is a worst case thing. In crypto, we don't want our systems to be unbreakable only in the worst case. We want them to be unbreakable at least in the average case. It would be better if it were unbreakable in the best case (or all cases). Another, related, issue we have is that of generating hard ...

Only top voted, non community-wiki answers of a minimum length are eligible