Trapdoor and RSA (Schneier)

Question

Disclaimer: I'm new to cryptography.

Background: From Applied Cryptography (Bruce Schneier), page 30 of 2^nd edition

A trapdoor one-way function is a special type of one-way function, one with a secret trapdoor. It is easy to compute in one direction and hard to compute in the other direction. But, if you know the secret, you can easily compute the function in the other direction. That is, it is easy to compute $f(x)$ given $x$, and hard to compute $x$ given $f(x)$. However, there is some secret information, $y$, such that given $f(x)$ and $y$ it is easy to compute $x$.

Question: From a high level (i.e., more formally), is the following correct?

m = message
i = input (e.g., public key)
t = trapdoor (e.g., private key)
h = one-way hash
f(m,i) = h
f(h,t) = m

---

Edit: Please see Schneier's use of a "one-way hash" on page 38 of the same reference:

(..) Alice signs the hash of the document. In this protocol, both the one-way hash function and the digital signature algorithm are agreed upon beforehand.

1. Alice produces a one-way hash of a document.
2. Alice encrypts the hash with her private key, thereby signing the document.
3. Alice sends the document and the signed hash to Bob.
4. Bob produces a one-way hash of the document that Alice sent. He then, using the digital signature algorithm, decrypts the signed hash with Alice’s public key. If the signed hash matches the hash he generated, the signature is valid.

Edit 2: Update, based on suggested answers:

x = message
i = input (e.g., public key)
t = trapdoor (e.g., private key)
h = one-way hash
f(x) = h
g(h,t) = x

Answer 1

No, neither of the two blocks of 6 equalities in the current version of the question are correctly describing either a trapdoor one-way function (first citation); or its use for public-key encryption; or signature of a message using a one-way hash and RSA (second citation).

The two citations are only distantly related. In particular, the "one-way hash" in the second citation is not a "trapdoor one-way function" as defined in the first citation.

We'll be illustrating the vocabulary in the first, then the second citation, in the context of RSA only; in each case, giving formulas as attempted in the question.

---

Assume a public/private RSA key pair has been established. The public key is $(N,e)$, and as its name implies is assumed known to everyone.

In the first citation:

• The "trapdoor one-way function" is the function $f$ that transforms $x$ into $f(x)=(x^e\bmod N)$; we'll note $c=f(x)$.
• "the secret" (also "some secret information"), is the private key $(N,d)$, which is noted $y$ (or equivalently: anything which knowledge allows factorization of $N$).
• Knowledge of the private key $y=(N,d)$ allows computing an $x$ from $c$, such that $c=f(x)$; that can be done as $x=g(c)=(c^d\bmod N)$; it turns out that if $c$ was established by choosing $x$ with $0\le x<N$ and computing $c=f(x)$, then computing $g(c)$ always give $x$.
• Doing the same without "the secret" is believed intractable, for random choice of $c$, or for $c$ chosen as $c=f(x)$ for random choice of $x$ assumed secret.
• "the secret trapdoor" (function) is the function $g$; notice that $g(f(x))=x$ if $0\le x<N$; and $f(g(c))=c$ if $0\le c<N$.

In textbook RSA public key encryption, $f$ is the encryption function, and $g$ is the decryption function. Encryption is public, while decryption requires knowledge of the secret trapdoor $y$.

The notation used in the question's equations uses a function with two arguments and derives both $f$ and $g$ from that. That is done by defining the RSA function as accepting as second argument the key (a pair of integers), as follows:

• $i=(N,e)\;\;$ (the public key)
• $y=(N,d)\;\;$ (the private key, unlocking the trapdoor)
• $r(z,(N,k))=(z^k\bmod N)\;\;$ ($r$ is the RSA function, $z$ and $k$ are variables)
• $x=\text{message}\;\;$ (the plaintext)
• $c=r(x,i)=f(x)\;\;$ (the ciphertext per textbook RSA public-key encryption)
• $x=r(c,y)=g(c)\;\;$ (the deciphered plaintext)

Note: this only illustrates textbook RSA public-key encryption, which is extremely insecure in many practical situation (e.g. $x$ is unknown, but known to belong to a known set, such as $\{\text{head},\text{tail}\}$, or a class roll). This is avoided in actual uses of RSA for encryption.

---

In the second citation, which describes signing a (possibly large) message using textbook RSA and a one-way hash function:

• "the one-way hash function" is a one-way function, noted $H$, which has no relation to RSA, and is assumed to not be a trapdoor one-way function in the sense of the first citation; rather, $H$ could be something like SHA-512.
• "document" is a message $m$, expressed as a bitstring (including, a file).
• "the hash of the document" (also "a one-way hash of a document" of step 1) is the result of applying $H$ to $m$, noted $h=H(m)$; that $h$ is assimilated to an integer, and $0\le h<N$ holds.
• In step 2, "Alice encrypts the hash with her private key" is poor terminology for: Alice applies the secret trapdoor function $g$ (as in our analysis of the first citation) to $h$; that yields $s=g(h)$.
• In step 3, "the signed hash" is that same $s=g(h)$.
• In step 4:
  • Bob computes "a one-way hash of the document that Alice sent"; that will be $h$ as originally computed by Alice if and only if the document that Bob received is exactly $m$ as Alice has processed it; the only if part is because $H$ is one-way (or, depending on threat model, collision-resistant).
  • (Bob) "decrypts the signed hash with Alice’s public key" is poor terminology for: Bob applies the trapdoor one-way function $f$ (as in our analysis of the first citation) to $s$ that it received from Alice, giving $f(s)$; in the absence of alteration of $s$, that will be $f(g(h))$, that is $h$ as originally computed by Alice.
  • Bob will consider that the document he received is as signed by Alice when these two computations of $h$ give the same result.

Again sticking to the notation in the question

• $i=(N,e)\;\;$ (Alice's public key)
• $y=(N,d)\;\;$ (Alice's private key, unlocking the trapdoor, known only to Alice)
• $r(z,(N,k))=(z^k\bmod N)\;\;$ ($r$ is the RSA function, $z$ and $k$ are variables)
• $m=\text{message}\;\;$ (the message to sign, approved by Alice)
• $h=H(m)\;\;$ (the hash of the message as computed by Alice)
• $s=r(h,y)=g(h)\;\;$ (the signature as computed by Alice)
• $(m,s)\;\;$ (the signed message that Alice sends)
• $(\tilde m,\tilde s)\;\;$ (the alleged signed message that Bob receives)
• $\tilde h=H(\tilde m)\;\;$ (the hash of the alleged message as computed by Bob)
• $\widehat h=r(\tilde s,i)=f(\tilde s)\;\;$ (the hash computed by Bob from the alleged signature)
• Bob accepts $\tilde m$ as genuine and signed by Alice if and only if $\tilde h=\widehat h$.

Signing is by applying the secret trapdoor function, and can be performed by Alice only; anyone knowing Alice's public key can perform the verification that Bob does.

Note: this only illustrates textbook RSA signature with hash, which has known security limitations; notably, if the width of $h$ was small enough (e.g. 256 bit as if SHA-256 is used for $H$), and Alice signs many messages specially crafted by Carol, then Carol can forge another message and its signature, even though Alice never signed that other message. This is avoided in actual uses of RSA for signature.

Answer 2

Your suggested formalization is not quite right. Also your notation isn't consistent with Schneier's.

Schneier calls the hash function $f$, the input $x$ and the trapdoor $y$. The hash value of $x$ is the image $f(x)$ of $x$ under $f$. In general it is very difficult to compute $x$ just from $f(x)$. There is an efficiently computable function $g$, however, such that $g(f(x), y) = x$. So if you insert the hash value and the trapdoor it spits out the original value.

What's problematic about your formalization is that $f$ should only take one value by Schneier's definition and that you don't differentiate between $f$ and $g$.