2
$\begingroup$

I have this textbook definition, I shall include below.

GenModulus denotes a ppt algorithm that, on input $1^n$, outputs $(N, p, q)$ where $N = p\,q$ and (except with negligible probability) $p$ and $q$ are $n$-bit primes.

A few pages back in the book, it did say $1^n$ was the security parameter, which I assume applies above.

My first question is, what exactly is an $n$-bit number? I assume, to use an example with decimals, that $3$-bit would be a number no greater than $111$ in binary which is $7$ in decimal.

My next question is, what do they mean by negligible probability within the context of this question? I assume it means the two prime numbers $p$ and $q$ are guessable by an adversary with negligible probability.

$\endgroup$
1
  • $\begingroup$ @kelalaka So they are saying there is negligible probability that p = q when those two primes get generated? Could you provide a number example for the n-bit, it would really help me visualise it? $\endgroup$ – questioner Feb 9 at 0:49
2
$\begingroup$

What exactly is an $n$‑bit number?

In the context, number designates an element $m$ of the set $\mathbb N$, the non-negative integers. Such $m$ is $n$‑bit if and only if $n\in\mathbb N$ and $\lfloor2^{n-1}\rfloor\le m<2^n$, or equivalently $n=\left\lceil\log_2(m+1)\right\rceil$. When $n\ne0$, that simplifies to $2^{n-1}\le m<2^n$, or equivalently $n=\left\lfloor\log_2(m)\right\rfloor+1$.

Any $n$‑bit $m$ in $\mathbb N$ has a unique $n$‑bit bitstring representation $x$ in binary per big-endian convention, and when $n>0$ the leading bit of $x$ is $1$. It holds $\|m\|=|x|=n$ per the notation in Katz&Lindell's Introduction to Modern Cryptography.

Any $n$‑bit bistring $x$ represents an at-most‑$n$‑bit $m$ in $\mathbb N$ per such convention. It holds $\|m\|\le|x|=n$ and $0\le m<2^n$. In some contexts¹, it's (slightly incorrectly) stated that such integer $m$ is $n$‑bit, when really $x$ is $n$‑bit and $m$ is at most $n$‑bit. The question is making just this when it states

$3$‑bit would be a number no greater than $111$ in binary which is $7$ in decimal.


What do they mean by negligible probability within the context of this question?

It means that for any polynomial $r$ (with positive leading coefficient²), for $n$ sufficiently large, the probability is less than $1/r(n)$ that it does not hold that $p$ and $q$ output by the algorithm are $n$‑bit primes.

Equivalently: for all $k>0$ exists $n_k$ such that $n>n_k$ implies that said probability is less than $1/n^k$.

Still equivalently: it is allowed only with probability bound to vanish when $n$ grows (and faster than any polynomial in $n$) that $p$ or/and $q$ are not prime, or/and are more or less than $n$‑bit.

Said probability is computed over all the inputs of the deterministic version of the Probabilistic Polynomial Time algorithm considered, where the randomness is explicitly introduced as an extra parameter, rather than implicit.


I assume it means the two prime numbers $p$ and $q$ are guessable by an adversary with negligible probability.

No. Nothing is stated in the definition quoted in the question about the probability that $p$ or $q$ can be guessed. That comes later in the text.

The probability in the definition is there to formally accommodate a probabilistic primality test, which can let a composite $p$ or $q$ creep out on rare occasions³. In practice, that probability is made so low that it's neglected.


¹ Including textbook RSA when dealing with the message rather than key generation.

² That's left implicit in Katz&Lindell's Introduction to Modern Cryptography, ed. 3, definition 3.4

³ It additionally allows $p$ or $q$ to occasionally not be $n$‑bit, as could be the case for $n<2$ (there's no prime less than $2$‑bit); or for primes generated as the smallest prime at least $m$ drawn uniformly at random in $[2^{n-1},2^n)$, which outputs a prime larger than $2^n$ with probability $O(n/2^n)$.

$\endgroup$
2
  • $\begingroup$ Thank you for clarifying the n-bit prime. For the p and q I do not understand if you are saying: sometimes it is not a real prime, or sometimes it is not n-bit size? $\endgroup$ – questioner Feb 9 at 12:51
  • $\begingroup$ @questioner: see updated answer after "Still equivalently" $\endgroup$ – fgrieu Feb 9 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.