Can an adversary distinguish a private key from a pseudo-random string of the same length? Apologies if this is a dumb question but allow me to describe the dilemma I have:

Suppose that I am protecting a private key on a device using a password & PBKDF2. The obvious attack would be an offline bruteforce by which an attacker would know the password used to protect the private key and would also have access to the private key.

For a very important & undisclosable reason, the password used to protect this private key has a small search space i.e. it is not complex and is of a short length.

The controls I have in my mind are:

Have the key pair generated on the device but send the public key to the backend. The public key will not be stored on the same device as the private key. This will mitigate the bruteforce attack as the attacker would not know if the decrypted blob is the private key without being able to correlate it to it's corresponding known public key. (Hope that makes sense)
Encrypt just the private key using PBKDF2 and provide no "Known Plaintext" to the adversary like -----BEGIN RSA PRIVATE KEY----- or -----END RSA PRIVATE KEY-----
The private key is used to generate a signature which is verified by the back end and this will have limited attempts thereby mitigating an offline attack
I will be using a salt and a slow derivation function

My hope is (and I could be wrong) is that the attacker would not be able to distinguish such a private key from other pseudorandom blobs received after decrypting it using various password attempts in a bruteforce attack. Am I correct in my understanding? Am I missing some fundamental mathematical understanding in the RSA cryptosystem or any asymmetric cryptosystem that debunks the above controls? I wish to understand if the distinguishability of a private key from a pseudorandom string (of the same length) is close to negligible.

Usually choosing a safe password and standard parameter for the PBKDF2 key derivation would be enough protect your cipher. If PBKDF2 is correctly used, the symmetric key you get as output is well generated and attacking the ciphertext is infeasible.

Protecting a private key as you're doing is a standard operation, usually the password is used (in PBKDF2) to generate a symmetric key which is used with a symetric algorithm (let's say AES) to protect your precious private key.
AES is supposed to be secure even if an attacker is given access to a decryption oracle (i.e.: it can get decryption of every ciphertext he wish but yours, the challenge). So modifiing the plaintext (stripping the header) would not improve the security level.

After your edit.
Let's imagine that someone saw almost all your password while you were typing it or know that it is included in a relatively small set.

You said that you would strip the "-----BEGIN RSA PRIVATE KEY-----" string, that means that the key is in PKCS#1 standard, so what you keep is a base64 encoded string corresponding the following DER structure:

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

(source)

So, an attacker could try to check for the value of $e$ (usually a standard value among 2 or 3) or check if $p \times q = n$, or ...
So even if, in theory an RSA key is just a couple of integers, it is usually stored in a well known structure helping the attacker to recognize what he has found.


How to make the range of modulo $p$ to $[-\frac{p}{2};\frac{p}{2}]$? I am using NTL (A Library for doing Number Theory) to implement a FHE (Fully Homomorphic Encryption) scheme. In general, the range of modulo p is  $[-\frac{p}{2};\frac{p}{2}]$ in FHE scheme. However, the range of modulo p is  $[-p,p]$ in NTL.

If I want to use the range that is $[-\frac{p}{2};\frac{p}{2}]$, how I can do it ?

If the value $x$ is in the set $\{0, 1, 2, .., p-1\}$, which is the "natural" set of residues moduli $p$, then, you just have to check if $x$ is greater than $\frac{p}{2}$ and if so, subtract $p$.

If $x$ does not belong to $\{0, 1, 2, .., p-1\}$, then you can first do the usual modular reduction to transform $x$ in a element of this set and then, do the subtraction if needed.

my_modular(x, p)
    if 0 <= x and x <= p-1
        if x > p/2
            return x - p
        else
            return x
    else
        new_x = x % p # usual modular operation
        return my_modular(new_x, p)

Notice that I am assuming the usual modular operation will not return negative values as you are saying the NTL's mod operation does.

Try to find a modular operation that return values in $\{0, 1, 2, .., p-1\}$.


How useful is proxy re-encryption if we end up needing a symmetric key? I'm trying to design a system using proxy re-encryption (PRE) to allow the sharing of data between a user (delegator) and other users he delegates access to (delegatees). The goal is to use a PRE scheme to prevent the sharing of the delegator's private key.

I wanted to have a DB where all data is encrypted, each delegator's data encrypted under his private key. If someone requests access to a delegator's data there are 2 options:

Has legitimate access permission, in which case data should be returned;
Doesn't have access to what was requested, data should not be returned;

The proxy would have a re-encryption key and the delegatee would have another key to convert the proxy's (partially decrypted) ciphertext to plaintext.

My problem: if I have my records encrypted under my symmetric key and I allow a delegatee to see that key (after the proxy partially decrypts that key, the definition of delegatee would mean he's someone who can finalise decryption), he can then have access to all delegator files.

I was thinking a solution could be to have each record encrypted under a different key, so the delegatee would only have access to the key which encrypts the files he requested. This seems like it would have insane computational/storage overheads.

Another alternative would be to have some sort of proxy to DB which could generate keys on fly and encrypt data before sending it to a valid delegatee. Problem here is that that data was encrypted in the DB so the proxy would have to be able to decrypt it before encrypting it again under this new key. This means the proxy would have to know the key, defeating the whole point of a PRE scheme (also, the delegator would not know the key which encrypts his own files, which is undesirable).

Finally, the reason I'm posting this here is because I believe this is related to the understanding of PRE schemes and how they can be used in practise.

Let's look at an example of proxy re-encryption:

User A encrypts a some specific number (which is the message) under their own public key producing ct.
User A sends ct to a proxy.
User A determines that users B and C should be able to decrypt ct and uses their public keys and A's secret key to produce two re-encryption keys which are sent to the proxy. The proxy doesn't have any secret key that can be used to decrypt ct and recover the number.
Users B and C can identify themselves against the proxy which will use the corresponding re-encryption keys to produce the final ct$_B$ or ct$_C$. The proxy must store all three versions of the ciphertext (original + two re-encrypted versions). The requesting users only get their corresponding ciphertext.
Users B and C can use their secret keys to decrypt their corresponding ciphertexts.

There is a size limit at which messages can be encrypted, because ElGamal-style schemes work in cyclic groups which permit only elements (numbers) of a specific size.

If we want to encrypt messages that are larger, we need to use some kind of strategy to wrap the whole large message in an additional security layer. This can be symmetric encryption. When combined with asymmetric encryption is called hybrid encryption.

User A generates a random AES key and encrypts the large message using AES under that AES key producing the symmetric ciphertext ct$_s$. Then the AES key is converted to a number and encrypted under their own public key producing the asymmetric ciphertext ct$_a$.
User A sends ct$_s$ and ct$_a$ to a proxy.
User A determines that users B and C should be able to decrypt ct and uses their public keys and A's secret key to produce two re-encryption keys which are sent to the proxy. The proxy doesn't have any secret key that can be used to decrypt ct$_s$ or ct$_a$ and recover the number or the original message.
Users B and C can identify themselves against the proxy which will use the corresponding re-encryption keys to produce the final ct$_{a,B}$ or ct$_{a,C}$. The proxy must store all three versions of the asymmetric ciphertext (original + two re-encrypted versions) and only one version of the symmetric ciphertext. Each requesting user receives the symmetric and their corresponding asymmetric ciphertext. For example, user B receives ct$_{a,B}$ and ct$_s$.
Users B and C can use their secret keys to decrypt their corresponding asymmetric ciphertexts and then use the recovered numbers to convert them to AES keys and decrypt the symmetric ciphertexts.

When the messages get large, only the asymmetric ciphertext requires additional processing and storage for each additional user. Depending on the used primitives, the asymmetric ciphertext typically has a size of 512 to 4096 bits. The size of the non-duplicated symmetric ciphertext almost the same as the size of the original message (differs only by a constant amount such as at most 256 bit for AES with a sensible mode).

The crucial part is that user A must generate a fresh and random AES key for each message they want to send if the recipients might be different. But this kind of key-wrap method can be used to deduplicate multiple messages further when they are always intended to be received by the same group of users. Then user A must assign each group of users a unique and random AES key (which doesn't leave the system of user A).


Distinct cleartexts that are invariant under encryption I'm really new in this whole cryptography thing. And while I was going through some articles about RSA I stumble upon a really weird thing and it goes like this:

  If $n = pq$ is a RSA modulus, and d is the encryption exponent. There are at least 9 distinct cleartexts m that are invariant under encryption, i.e. $m^d\ ≡\ m\ (mod\ n)$ ?

Why is it at least 9, can it be more ? And is there any proof for this ?

I seem really interesting and I would like to know the answer on this. If anyone can answer it would be so helpful.

Why is it at least 9?

Actually, we have to assume that $p$ and $q$ are distinct odd primes, and that $d$ is odd; this is presumably covered by the assertion that $n = pq$ is an RSA modulus.

With that assumption, we can proceed as follows: we have $m^d \equiv m \pmod n$ iff both these hold:

$$m^d \equiv m \pmod p$$

$$m^d \equiv m \pmod q$$

This is a consequence of the Chinese Remainder Theorem, which we'll be using a lot.

For the relation $m^d \equiv m \pmod p$, for odd prime $p$, we have at least 3 values of $m \bmod p$ that satistify it, namely $m \equiv 0, 1, p-1 \bmod p$ (and the later is often written as $-1$, as $p-1 \equiv -1 \pmod p$).

Similarly, we have at least 3 values of $m \bmod q$ that satify $m^d \equiv m \pmod q$, $0, 1, -1 \pmod q$.

Now, by the Chinese Remainder Theorem, and because $p, q$ are relatively prime, then for any pair of integers $a, b$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.

As a consequence, for any one if the values $a \in \{0, 1, -1\}$, and any one of the values $b \in \{0, 1, -1\}$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.  Such an $m$ satisfies both of our original relations modulo $p, q$, and hence satisifies $m^d \equiv m \pmod n$.

There are a total of 9 such sets of $a, b$ values, and hence 9 such values of $m$.

  can it be more ?

Actually, if we have $d = 3$ (or if $d$ is the decryption exponent corresponding to $e = 3$), then no, we can't; for the relation $m^3 = m \pmod p$, there can only be at most 3 solutions (as $p$ is prime); as we have listed 3 such solutions, that must be all of them (and similarly for $q$).

However, if we consider larger values of $d$, then yes, there can certainly be more.  As an example, if we have $pq = 65$ and $d = 5$, there happens to be 25 such 'value preserving cleartexts' (and it should be easy to reconstruct why this is).

  And is there any proof for this ?

The above explination can be expanded to a formal proof; if you want, you can find explicit representations of all 9.


Is the hash-based commitment IND-CPA? As we know the well-known hash-based commitment is as follows:

Prover: given a message $m$, it:

(1) picks a fresh random value $r$

(2) computes $H(r||m)=c$.
Verifier: given $c$ and the commitment opening: $(r,m)$, checks $H(r||m)=c$

Question: Am I right that in the random oracle model, the above scheme is IND-CPA?

Indistinguishability under chosen message attacks (IND-CPA) is a security definition for encryption schemes and not for commitments. So we cannot claim that a commitment scheme is IND-CPA.

Notice that the above scheme cannot be an encryption since there is no encryption/decryption key. In fact, if the hash function has a larger domain than range, there may be multiple pairs $(m,r)$ that map to the same $c$ and one cannot know which one is the correct (even if they were all powerful).

It is true, however, that the scheme you propose is hiding: for any two messages $m_0,m_1$ it holds that $H(r,m_0)$ and $H(r,m_1)$ are indistinguishable in the random oracle model.


Can I use PBKDF2 as a stream cipher? Unfortunately I have to implement some naive homemade symmetric crypto, since ordinary AES CTR is not implemented in available API on target platform.

What I’m going to do is, given encryption password and plaintext bytes, generate “encryption key” from password via PBKDF2/RFC 2898 with length of plaintext, and then XOR this “gamma” against plaintext bytes.

Could you please criticize this approach and enumerate vulnerabilities and issues?

TL;DR: Yes, you can use PBKDF2 as a stream cipher.  However, you should not use it for that and for its intended purpose (i.e. password-based key derivation) at the same time.  Instead, if you need to do both, call it twice.

PBKDF2 is a password-based key derivation function — or, rather, a scheme for constructing such a function out of a variable-key-length PRF, which in turn is is usually implemented by taking a cryptographic hash function and wrapping it in the HMAC construction.

As a general-purpose key derivation function, PBKDF2 is designed be able to generate an arbitrarily long* string of pseudorandom bits.  To make it resistant to brute force password guessing, it is also designed to take an iteration count that deliberately slows it down.

However, when used to generate more output than the underlying PRF / hash function produces, PBKDF2 has what is nowadays generally considered to be a design flaw: its runtime is roughly proportional to the product of the iteration count and the length of output requested (whereas, in many real-world scenarios, the time for an attacker to test one guessed password still only depends on the iteration count).  Thus, you really don't want to call PBKDF2 with both a high iteration count and a high output length.

Instead, my general recommendation** for applications that need to generate large amounts of key material using PBKDF2 is to first use PBKDF2 with a large iteration count to generate a "master key" whose size equals the output size of the underlying hash (which should preferable be chosen to make this as large as feasible, e.g. SHA-512 for a 512-bit output), and then feed this master key into a non-iterated KDF (such as HKDF-Expand from RFC 5896, or even PBKDF2 itself with the iteration count set to 1) to expand it into the full required length.

With this scheme, the output of PBKDF2 applied to the master key, with a unique per-message salt and an iteration count of 1, should even be safe to use directly as a keystream to XOR the message with.  Internally, PBKDF2 simply uses (salted and optionally iterated) HMAC in counter mode, which yields a secure stream cipher as long as the underlying hash function satisfies the conditions of the HMAC security proof (which all secure modern hashes, and even some old not-so-secure ones like SHA-1 and even MD5, are believed to do).

You do need to ensure that the salt input to PBKDF2 is unique for each message; otherwise you end up reusing the same keystream for two messages, which breaks the security of any XOR-based stream cipher.

Also, note that, like any XOR stream cipher, this construction does not protect message integrity, and in fact is highly malleable.  To protect against active attacker, you need to combine the encryption scheme with a message authentication code.  Fortunately, you already have one available, namely HMAC.  So just run the XORed ciphertext through HMAC again (preferably with a separate key derived from the master key), append the result to the message, and verify it before decryption, and you're all set.

Indeed, if you really cannot access the underlying HMAC function, even PBKDF2 itself (being really just a thin wrapper around HMAC) could be used as a MAC, by passing the message to be authenticated as the salt parameter and requesting one hash block of output.  While this won't quite produce the same output as raw HMAC (since, even with the iteration count set to 1, PBKDF2 still appends the block counter to the salt), the security proof carries over trivially.

If you wanted to get fancy, you could even use HMAC (or PBKDF2) in the SIV construction as both the MAC / nonce generator and as the encryption primitive.  So, as perverse as it may seem, the following pseudocode should implement a secure misuse-resistant AEAD scheme using nothing but PBKDF2:

// a variable-length PRF, implemented using PBKDF2 with an iteration count of 1
function prf(key, data, len):
    return PBKDF2(key, data, 1, len)

// SIV authenticator / IV length in bytes (32 bytes = 256 bits)
constant token_size = 32

// internal MAC output length, may be larger than token_size
constant internal_mac_size = max(token_size, PBKDF2_hash_block_size)

function SIV_PBKDF2_encrypt(key, plaintext, assoc_data, nonce):
    macP = prf(key, "macP" + plaintext, internal_mac_size)
    macA = prf(key, "macA" + assoc_data, internal_mac_size)
    token = prf(key, "auth" + macP + macA + nonce, token_size)
    ciphertext = plaintext XOR prf(key, "encr" + token, length(plaintext))
    return (token, ciphertext)

function SIV_PBKDF2_decrypt(key, token, ciphertext, assoc_data, nonce):
    plaintext = ciphertext XOR prf(key, "encr" + token, length(ciphertext))
    macP = prf(key, "macP" + plaintext, internal_mac_size)
    macA = prf(key, "macA" + assoc_data, internal_mac_size)
    if token != prf(key, "auth" + macP + macA + nonce, token_size):
        return ERROR
    else:
        return plaintext

In the code above, all variables are assumed to be byte strings of arbitrary length, and may contain null bytes.  The + operator always denotes string concatenation.  Note that the length of the left argument to + above is always fixed, making the concatenated result unambiguous.

The ERROR constant stands for some unambiguous indication of decryption failure, possibly due to malicious input; instead of a special return value, one could also e.g. throw an exception in that case.  The important things is that, however it is implemented, such a failure should not reveal anything about the invalid plaintext string to the caller, as the content of that string may be manipulated by an attacker.

If a distinct nonce is provided for every encrypted message, this code should implement (modulo any possible implementation bugs) an IND-CCA secure authenticated encryption scheme.  Even if the nonce is repeated or omitted, it should still implement a "deterministic authenticated encryption" scheme, in the sense of Rogaway and Shrimpton, essentially meaning that the only information it leaks (besides message length, which all arbitrary-length encryption schemes reveal to some extent) is whether two encrypted messages are identical or not.

The length of the key input is arbitrary, but should be sufficient to resist brute-force guessing attacks (i.e. at least 128 bits, preferably more).  It should not be a user-supplied password — you'll want to run those through PBKDF2 (or some other password-based KDF) with a high iteration count first.

As an optimization, the internal macA variable may be precomputed if the associated data is known in advance; other similar optimizations, as in Rogaway's original SIV scheme, are also possible.

*) Technically, the output length of PBKDF2 is limited to $2^{32}-1$ times the output length of the underlying PRF / hash.

**) Assuming that one cannot or will not switch to a more modern password-based KDF, such as scrypt, Argon2, Catena or Balloon hashing.  Unlike PBKDF2, all of these KDFs are designed to also consume large amounts of memory, which makes them more resistant to massively parallel brute force attacks using GPUs, FPGAs or ASICs.  As a side effect, they also intrinsically support efficient generation of large amounts of output key material.


How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem? In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$.

My question is, how this condition ($s \geq 8$) is obtained? I guess this lower-bound on $s$ relates to the smoothing parameter, but I can't figure out how it is determined?

Note: I edited a lot of my speculation and calculations after comments from Chris Peikert (see comments below).

The smoothing parameter on a lattice, $\eta_\epsilon(\Lambda)$, is roughly the width of a discrete Gaussian $\mathcal{D}_{\Lambda,s}$ above which it is well-approximated by a continuous Gaussian; see the Regev quote on page 17 here.

In particular, for $\mathbb{Z}^n$, there is an upper bound for the smoothing parameter (see page 8):

$\eta_\epsilon(\mathbb{Z}^n) \leq \sqrt{\ln(2n(1 + 1/\epsilon))/\pi}$

Again, on page 17, if $s \geq \sqrt{2} \eta_\epsilon(\mathbb{Z}^n)$, then the sum of the discrete Gaussian $\mathcal{D}_{\Lambda,s}$ and a continuous Gaussian with width $s$ is basically equivalent ("within statistical distance $4\epsilon$") to a continous Gaussian of width $\sqrt{2} s$, and you want this to hide the discrete structure in the continuous noise.

So I thought at first that the critical quantity was $\sqrt{2} \eta_\epsilon(\mathbb{Z}^n)$. However! After a comment from one of the authors of the paper (see comments below!), it's enough to just consider $s \geq \eta_\epsilon$ with $\epsilon \ll 1/2$. Using the formula above with $\epsilon = 2^{-256}$:

$n=128 \rightarrow s \geq 7.63$
$n=1024 \rightarrow s \geq 7.68$
$n=2048 \rightarrow s \geq 7.89$

So $\eta_\epsilon$ doesn't fluctuate that much and you can take $s \geq 8$ for a nice round number.

Of course you can vary $\epsilon$; I used Lemma 4.2 in this paper to justify constraining it $0 < \epsilon < 1$, but it should be a negligible function, like $\epsilon = 2^{-n}$.

Thanks to Chris Peikert for discussion and clarification in the comments!


Why is $-1$ an illegal message in the Goldwasser-Micali Encryption Scheme I'm not sure why in the Goldwasser-Micali encryption scheme with a Blum integer $N$, the message $-1$ is always a illegal message.

Can you give me some direction for starting?

What is illegal message's meaning?

I'm going to use the notation from here.

I'm still not sure why one wants to handle $-1$ as a message, but anyways. Simple solution is that you simply define: if message is $-1$ set message to $1$ and the other way round when decrypting. Second point is that you can only encrypt messages from a message space with two elements (independent from how you name them).

Ok, but maybe this is the question/answer:

Basically the idea is that you encrypt a message bit by bit and the security of the encryption scheme relies on the quadratic residuosity problem.

That is, it is hard to distinguish between quadratic residues modulo $n=pq$ for primes $p$ and $q$ (the set is denoted as $QR_n$) and pseudo-squares modulo $n$. Thereby, a pseudo-square $x$ modulo $n$ is an element with Jacobi symbol $\left( \frac{x}{n} \right)=1$. This means that from the Jacobi symbol it looks like a quadratic residue, but actually it belongs to the set of quadratic non-residues ($QNR_n$), i.e., it is a quadratic non-residue modulo $p$ as well as modulo $q$, giving $\left( \frac{x}{n} \right)=\left( \frac{x}{p} \right)\cdot \left( \frac{x}{q} \right)=(-1)\cdot(-1)=1$.

However, without knowing the factorization of $n$, i.e., $p$ and $q$, which would allow us to compute the Legendre symbols $\left( \frac{x}{p} \right)$ and $\left( \frac{x}{q} \right)$, we cannot decide whether $x$ is a square or a pseudo-square.

Now, such a pseudo square $x$ and $n$ is the public key and the factorization $p,q$ is the private key. Taking $n$ as Blum integer has the reason that you can efficiently find such an $x$ (i.e., set $x=N-1$).

Encrypting amounts to chosing a random square $y^2$ for $y$ random from $Z_n^*$ and for message $m\in\{0,1\}$ we compute $c=y^2x^m \pmod n$. This means

if $m=1$: $c=y^2x \pmod n$ (gives a non-square, but with Jacobi symbol 1)
if $m=0$: $c=y^2 \pmod n$ (gives a square)

Now, by the quadratic residuosity assumption, without knowing $p$ and $q$ given the public key and $c$, one cannot decide whether $c$ contains an encryption of $1$ or $0$.

Decrypting is simply deciding whether $c$ is in $QR_n$ (giving $m=0$) or in $QNR_n$ (giving $m=1$).

Your question is now: what if we use message space $M=\{0,-1\}$? When taking $m=-1$, we would have $c=y^2x^{-1}$, i.e., we can interpret this as using the inverse $x^{-1}$ of $x$ modulo $n$. The question is: Would this also be a pseudo-square?

Now, we know that $x\cdot x^{-1} \equiv 1 \pmod n$ and we know that the $\left( \frac{1}{n} \right)=1$ ($1$ is in $QR_n$) and we know that for $a\equiv b \pmod n$ we have that $\left( \frac{a}{n} \right)=\left( \frac{b}{n} \right)$. This and the fact that the Jacobi symbol is multiplicative gives us that:

$\left( \frac{x\cdot x^{-1}}{n} \right)=\left( \frac{x}{n} \right)\cdot \left( \frac{x^{-1}}{n} \right)=1$. Now, we know the Jacobi symbol of $x$, which gives us

$1\cdot \left( \frac{x^{-1}}{n} \right)=1$. However, since $x$ is in $QNR_n$ and $1$ is in $QR_n$, $x^{-1}$ must be in $QNR_n$. Since it, however, must have a Jacobi symbol of $1$ is must be a pseudo-square.

So, yes, GM encryption would technically also work for $M=\{0,-1\}$ (but you could then give $x^{-1}$ instead of $x$ in the public key and work with $M=\{0,1\}$ again). I see no real reason why one should do that anyways (costs an extra inversion). Maybe there is an (obvious) security problem if you have $x$ in the public key and use $x^{-1}$ in the encryption, which I do not see at the moment.


Reversed One-Time-Password - generating secret server side In our company we're thinking about a new auth scheme (not a 2FA!) where vault is secured by secret. User should be able to access the vault just by typing the One-Time-Password (OTP) into the webform.

Here is the theory as I understand the normal OTP works:

generated secret is stored on both the server and user's auth app
some function now accept time and secret and generate OTP (6 digits)
server verify if the OTP entered by the user matches the server generated OTP in the same time slot

`

          client                          server
          ======                          ======

         +------+                        +------+
  time -->      |                        |      <-- time
         |  fn  +--> OTP          OTP <--+  fn  |
secret -->      |                        |      <-- secret
         +------+     ^            ^     +------+
                      |            |
                      +- matches? -+

I was thinking if this scheme can be anyhow turned around like this:

`

          client                          server
          ======                          ======

         +------+                        +------+
  time -->      |                 time -->      |
         |  fn  +--> OTP -----+          |  fn' +--> secret
secret -->      |             +---------->      |
         +------+                        +------+

That way our server application will not store the secret anyhow and we get nice familiar UX for users to unlock the vault.
Is it possible to reverse the OTP algorithm like this?

No, that can't work. Reasons:

There would still be the need to compare secret out of fn' against some reference in order to determine if it is correct, hence something confidential in the server (a comment has clarified this is not an issue in the application)
One Time Passwords are short and have little entropy, secrets are longer/have more entropy, and fn' is thus impossible by an information-theoretic argument.
The time is not always the same on the client and server. That issue also occurs for normal OTP, and has various workarounds (trying variations of time, or/and replacing time with an incremental counter which additionally saves on timekeeping power consumption on the client's OTP device).
[Addition] If fn' was public, then knowledge of one OTP and time would be enough to reconstruct secret, allowing to forge other OTPs (assuming fn is public or OTPs are short). That goes against a basic requirement in OTP authentication.


DIY message level security? This might be in danger of being too elementary a question for this community but I'm hoping for expert help:

Assuming that TLS is not enough to protect messages transmitted between a client and a server, what is a good way to establish secure communication between a client and a server?  In my case this is between a web server and a mobile app, with typical requests and responses between the two.

I have the following idea:  Generate an asymmetric key pair, distribute the public key with the mobile client and keep the private key on the server.  When initiating communication with the server from the client I could generate a symmetric key for the session, encrypt the key using the public key, send the encrypted key to the server which would then decrypt the symmetric key using the private asymmetric key, and then continue to decrypt requests and encrypt responses using the symmetric key.

Is this anywhere close to an acceptable solution, what are the nuances I should be aware of to achieve an acceptable solution? What algorithm choices should be made?

Your idea lacks forward secrecy, which protocols like TLS often (in newer versions anyway) offer. Otherwise it is close to how such things are usually done.

To get forward secrecy you would instead use an ephemeral Diffie-Hellman key exchange, which you would authenticate with the pre-shared public key (which would be a signing key, not an encryption key, where that makes a difference).

There are several alternatives for algorithms, but basically you should... do what good TLS cipher suites do. E.g. ECDH or EDH with either ECDSA or RSA signatures. AES-GCM would be a good default choice for symmetric encryption.


When extending the domain of a fixed-length MAC, why do we have to include the message length in each block? In Katz's text (2nd edition), it states in 4.3.2:

  The truncation attack can be thwarted by additionally authenticating
  the message length along with each block. (Authenticating the message
  length as a separate block does not work. Do you see why?) That
  is, compute $t_{i} = Mac'_{k}(l||m||i)$ for all $i$, where $l$ denotes the length
  of the message in bits. (Once again, the block length $|mi|$ will need to
  decrease.) This scheme is vulnerable to a “mix-and-match” attack...

I don't understand the "do you see why" part. Why can't we just use the first block to provide the length, and a tag along with it to authenticate the length, and an index to verify that it is the first block? For later blocks, we just give  the message and the index, and don't have to give the length, since it was already given in the first block.

I suspect it is because you can still do a truncation attack under specific circumstances. Say an adversary obtains the tag of another message m' that is shorter than the original message m. Then the adversary can replace the first block from m (the one containing the length) with the first block from m', and also replace the first element in the tag for m with the first element from the tag for m'.

Similary, if the message m' is larger, then a message extension attack becomes possible...


A questions about SP 800-90A DRBG additional input There is four inputs in SP 800-90A DRBG that is entropy sources, nonce, personailisation string, additional input.

I noticed the soundness of entropy_sources is most important thing for DRBG security and then nonce and last is  personalisation string.

I am wonder why additional input is needed? because entropy source is the key for security.

Here is my question

please give me an example of additional input for software cryptographic library (for linux, windows, anything..)
Is additional input is crucial to DRBG security?

Some (hopefully) useful information to what you ask can be found in sections 7.2 Other Inputs and section 8.7.2 Additional Input of the SP 800-90A Rev. 1   June 2015   Recommendation for Random Number Generation Using Deterministic Random Bit Generators standard at http://dx.doi.org/10.6028/NIST.SP.800-90Ar1.

I copied and pasted a couple of points which I hope will shed some light, but I would recommend reading those sections in full.

7.2:
Other information may be obtained by a DRBG mechanism as input. This information may or may not be required to be kept secret by a consuming application; however, the security of the DRBG itself does not rely on the secrecy of this information.
...
Additional input may also be provided during reseeding and when pseudorandom bits are requested. See Section 8.7.2 for a discussion of this input.

8.7.2:
Additional input may optionally be provided to the reseed and generate functions during requests. The additional input may be obtained from inside or outside a cryptographic module, and may include secret or public information. Note that a DRBG does not rely on additional input to provide entropy, even though entropy could be provided in the additional input, and
knowledge of the additional input by an adversary does not degrade the security strength of a DRBG.

I'm not sure of real world examples.


Weak one way functions from strong one way functions I'm stuck in a simple question about weak one way functions.

Suppose $f(x)$ is strong one way, is $g(x)=f(x)_0$, i.e. taking the first bit of $f(x)$ a weak one way function? Intuitively, it is, because for any adversary $\mathcal{A}$ the probability of inverting $g$ is $\frac{1}{2} + \epsilon$. So it seems safe to say $g$ is $\frac{2}{3}$-one way.

But apparently one cannot reduce inverting $g$ to inverting $f$, which leaves me no way to prove that statement by reduction. Am I getting it wrong?

No, $g$ is certainly not even weakly one-way. In particular, in order to invert $g$ you just need to be able to sample a $y$ such that the first bit of $f(y)$ equals the first bit of $f(x)$. Now, since one-way functions work on random input, it is clearly not hard to sample an input with the same first input bit as $f(x)$, since $x$ was randomly chosen.


Inverting RSA function I am in high school and I am writing a paper on RSA. I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered.
How is this done? I have tried to read the Handbook of Applied Cryptography but it's not making sense...

Would this be inversion:
Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.

I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered.

That is not known to be true; as long as the modulus is large enough to make factorization infeasible, there is no known way to compute e-th roots in general.

Now, if the plaintext $p$ is small enough that $p^e < N$, then it is easy to recover $p$ (just take the e-th root over the integers, which is an easy problem).  That's as close as we know to the result you're trying to get.

  Would this be inversion: Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.

If $N$ is small enough to make work in a practical amount of time, then $N$ is small enough to factor.


Is there a tangible benefit in keeping the number of PBKDF iterations secret and not storing them with the ciphertext? Suppose I have a local file and it is encrypted with a symmetric key derived from a strong passphrase, unique salt and $x$ number of PBKDF (e.g. Scrypt) iterations. I am interested in keeping this file a secret for a very long time.

Suppose the user specifies the number of iterations themselves e.g. a random number between the lowest safe number e.g. 1000 to the highest feasible number e.g. 100,000 when they first encrypt the file. The number of iterations would not be hard coded into the program or stored alongside the salt and encrypted data. It would be remembered only by the user and entered as a separate parameter along with the passphrase when it comes time to decrypt the file.

If an attacker were to gain a hold of the storage device to perform an offline attack on the file's encryption, my thoughts are that this makes their job much harder:

They still need to try all the possible permutations of each
passphrase
Each brute force attempt takes ~200ms due to the slow
PBKDF
They also do not know the exact number of iterations to try
either and have to try each passphrase permutation and repeat the
process for every iteration count.

The use case is that for day-to-day use the user stores the number of iterations alongside the salt and encrypyted data for ease of use and fast access. But when they are travelling and need to cross country borders where there is a possibility of their phone/laptop/device being confiscated, then they can choose to not store the number of iterations as an additional precaution.

The difficulty for the user is remembering the number of iterations to use as well as the passphrase. However this is just a small additional number to remember e.g. similar to a 4-5 digit PIN number. For some examples it could easily be written down on a random piece of paper, or added as a phone number to an entry in your address book. In other words, very easy to hide in plain sight and not likely confiscated along with the digital devices.

Another advantage is if the encryption uses a cascade of PBKDFs to produce a final derived key e.g. 7328 iterations of PBKDF2-SHA2 then feed the result of that into Scrypt with 4755 iterations. Now the user remembers the two numbers (or stores them in the address book) but it has a multiplier effect on the cracking difficulty for the attacker.

Do you concur that this is a reasonable feature to have in an encryption program?
Can you quantify how much additional security is gained from keeping the number of iterations secret from an attacker as well e.g. $n$ bits?

I don't think it is a good idea, for two main reasons.

Firstly, you are basing your security on the obscurity of a parameter that was not designed initially for being secret, which is a risky practice. It is similar to hiding the salt.

Secondly, following your example, you may in principle think that a random number of iterations between 10 and 100,000 is providing you with (roughly) 17 bits of additional entropy. That is, in addition to your initial secret password (with $K$ bits of entropy), you have to store the number of iterations, so your final secret is $K+17$ bits long. However, you are not actually gaining that additional level of security, since the iterative process for key derivation is, indeed, iterative, and for each password attempt, the partial results of each iteration can be reused for the next one.

The cost of a brute-force attack against a standard key derivation method will roughly be $2^p\cdot C \cdot N$, where $p$ is the bit length of the initial password, $C$ is the cost of each iteration (typically a hash-based function), and $N$ is the default number of iterations (e.g., 1000 iterations).

The cost of a brute-force attack against your approach will roughly be $2^p\cdot C \cdot 2^{17} = 2^{p+17}\cdot C$, since for each password you will perform $2^{17}$ iterations in the worst case. That is, your approach is, in the worst case for the attacker, equivalent to the standard one with the "highest feasible number of iterations" (as you put it in the question). To see this, consider the following example of brute-force attack to your approach: the attacker is trying different possible passwords (first "aaaaa", next "aaaab", etc.). In your approach, the attacker doesn't know the number of iterations. Let's assume she is trying the i-th password, for instance, "aabhjk". It is clear that the attacker cannot reuse the work for previous passwords. The attacker starts brute-forcing "aabhjk" with the minimum number of iterations (1000), with no luck. Next, she has to try "aabhjk" for 1001 iterations, but she doesn't start from scratch. She reuses the work done before with the 1000 iterations, and perform an additional one. This strategy is repeated until reaching "the highest feasible number of iterations", as you put it. That is why, at the end, your approach is similar (in terms of a brute-force attack) to simply using a very high number of iterations.

If instead of following your approach, you append those extra bits (i.e., the bits required for storing the number of iterations) to your password, and simply use the standard key derivation method, then the cost of a brute-force attack is $2^{p+17}\cdot C \cdot N$.

That is, your approach is, in fact, weaker than simply using the number of iterations as a suffix to the password. From a quantitative perspective, it could be approximately $N$ times weaker, where $N$ is the default number of iterations.


Encoding scalar values to points on Ed25519 I'm interested exploring key derivation and threshold signature protocol that require point arithmetic (addition) on the private scalar values and $S$ values of the signatures in ed25519.

Specifically what I would like to be able to do

Generate two eddsa private keys: (pub_1,key_1), (pub_2,key_2)
Compute the private scalar for each. key_1 -> exp_key_1 , key2 -> exp_key_2
Convert the keys to ed25519 points. exp_key_1 -> pt_1, exp_key_2 ->pt_2
Add the points to each other to get a third point. pt_1 + pt_2 -> pt_3
The sum of the points multiplied by the base point is expected to equal sum of the original public keys. Knowing how to convert the sum of the points to the base point would also be nice  pt_3 * G == pub_1 + pub_2

The part of the this process that is least clear to me is step 3.

The ref10 code makes it easy to do point arithmetic on public key. Just decode and do the add point addition as per question “Point addition and doubling in Ed25519 (ref10)?”

Using the raw bytes to Point decoder on the scalar fails about half the time and when it succeeds the expected homomorphisms don't hold; i.e.: $(a+b)\times G == A+B$

I'm aware the libsecp256k1 makes these sorts of manipulations very easy. I think it would be useful to be that on curve25519.

The problem may that ed25519-donna uses a decompression that inverts points. That's fixable, but from the description of the problem I think you might be mangling the point encoding somehow, and it isn't quite clear how.


Proof that no DES key makes encryption identity How can we prove that no DES key makes encryption the identity function?
That is: $\;\forall K\in\{0,1\}^{56}\quad\exists M\in\{0,1\}^{64}\quad E_K(M)\ne M$
Note: anyone disproving this proposition would gain instant celebrity, which is a meta-proof that this proposition is true, but not an acceptable answer!

That proposition is false for 2DES (EE), even restricted to one key, because twice  applying encryption with the all-zero key (and the Final Swap built into the Final Permutation) yields identity.
For the same reason, the proposition would be enough to prove that DES is not closed under function composition, hence not a group [but Keith W. Campbell and Michael J. Wiener's DES is not a group in proceedings of Crypto 1992 (free access) also proves other facts. See a more extended bibliography there].
Variants of the question:

3DES (EDE) with 3 or 2 keys
3DES EEE variant
what if we remove the Final Swap of the Final Permutation (then the proposition becomes very plausible for 2DES)
$r\ge1$ rounds of DES and independent subkeys, with or without Final Swap; clearly the proposition must become false for some $r$ !

Inspired by this question.

Update: towards a solution, I have thought of

Pure brute force. Plausibly, that requires no (or very little) more than $2^{55}$ DES encryption of a constant plaintext block $M_0$, say all zero (for we can fix a key bit thanks to the DES complementation property, and a single test is enough to eliminate overwhelmingly most keys). Using the all-zero block for $M_0$, or any one invariant under final swap, has the advantage that we can answer the question for DES both with and without final swap using essentially the same amount of work.
Some work reduction, possible by enumerating the keys in a way that allows caching of the external rounds (as was done in DESCHALL, see this).
Devising a function $F:\{0,1\}^{56}\to\{0,1\}^{64}$ that slightly simplifies the evaluation of $E_K(F(K))=\!\!\!\!?\;\,F(K)$ compared to that of $E_K(M_0)=\!\!\!\!?\;\,M_0$; it seems possible to save even more work.
Expressing the problem as a Boolean satisfiability problem in Conjunctive Normal Form and throwing a state of the art solver at it. I'm pessimistic about this approach, though.

Update2: the brute force approach might have been carried as early as 1999, when:

The EFF DES cracker first solved a challenge posed more than a year ago by world-renowned cryptographer and AT&T; Labs research scientist, Matt Blaze. The "Blaze Challenge" was designed to only be solvable by "brute force" cryptanalysis of DES. Mr. Blaze challenged the world to find matching pairs of plaintext and ciphertext numbers, consisting of nothing but repeated digits. Blaze himself was unaware of any such pairs until the EFF DES Cracker revealed the first known pair. It found that a hexadecimal key of 0E 32 92 32 EA 6D 0D 73 turns a plaintext of 8787878787878787 into the ciphertext 0000000000000000.

That's nearly enough to prove the question's proposition. What's missing is  that the key found is the only solution of the Blaze challenge with all-zero ciphertext, or making an exhaustive list of those that do and ruling each out from being counterexample to the proposition.

To throw something, here are simple proofs for 2-4 rounds, applicable to almost any Feistel Network. Some notation: $F_i$ denotes $i$-th Feistel round without swaps, $f_i$ denotes the Feistel function at $i$-th round, $S$ denotes the swap.
Since the initial permutation IP and the final permutation FP are inverses of each other, we can strip them away: for any bijection $P$:
$$P^{-1} \circ G \circ P = Id ~~~\Leftrightarrow~~~ G = Id.$$
We will use this trick later.
(2 rounds)

Consider a 2-round Feistel network (like in DES, with no swaps in the beginning and in the end), denote it by $G$. We want to check if it holds that
$$\forall a,b \in \mathbb{F}_{32} ~~~ G(a,b) = a,b.$$
The right output half is equal to $a \oplus f_1(b)$. This can not always equal $b$ for any $a$ (consider two distinct $a$).
(3 rounds)

Consider a 3-round Feistel network. The right half in the middle is equal to $a \oplus f_1(b)$ (from the input) and to $a \oplus f_3(b)$ (from the output). It follows that $f_1(b) = f_3(b)$ for all $b$. We can now use the trick again and remove symmetrically the first and the last round and the two middle swaps. We end up with $F_2(a,b) := (a \oplus f(b), b)$. Due to the nonlinearity of $f$ in DES, there exist no keys such that $f_2$ (and so $F_2$) is an identity (the key is only xored at the input of $f$).
(4 rounds)

Note that $(S\circ F_1)(a, b) = (b, *)$, and $(S \circ F_4^{-1})(a, b) = (b, *)$, where $*$ denotes a wildcard. So it sufficient to show that there are no 2-round FN that for all $b,x\in \mathbb{F}_{2^{32}}$ always map $(b, x)$ to $(b, y)$ for some $y \in \mathbb{F}_{2^{32}}$. For the two middle rounds we get 2 equations:
$$
b \oplus f_2(x) = y,
$$
$$
b \oplus f_3(y) = x.
$$
If in the input we change $b$ to $b\oplus \delta$ and don't change $x$, then $y$ has to change to $y \oplus \delta$ (from the first equation). From the second equation, we must have
$$b \oplus \delta \oplus f_3(y\oplus \delta) = x,$$
and so
$$f_3(y \oplus \delta) \oplus f_3(y) = \delta.$$
Since this must hold for all $y$, we obtain that $f_3$ must be a XOR with a constant, which obviously does not hold for DES rounds.


Why is it allowed to Generate Keys inside the game? I am studying reductions to prove security of crypto systems. Generally "games" are used for the proofs. For example, the next image was extracted from the page 91 of the book Post-Quantum Cryptography. Here, an adversary is constructed against Lamport-Diffie signature using a Forger with access to an oracle.

My question is why is it permitted to the adversary to generate keys? I make this question because the step 1 of this Algorithm calls the key generation process.

The adversary is permitted to generate the keys

because we're not restricting the adversary's internals.

(For example, the adversary is also permitted to compute the parity of y,

and to generate a random element of {45,56,62,68}.)


McEliece cryptosystem There is something intriguing me about this cryptosystem. That is :

Let $(S, G, P)$ be the secret key:
$S$ : invertible matrix
$G$ : generator matrix for some linear code $C$
$P$ : permutation matrix

And let $G'= SGP$ be the public key.

To encrypt $m$, we compute $Enc(m) = mG'+e$, with $e$ an error vector

The thing is, the basic idea about structural attacks, is that we brute-force the family of codes used (most likely, the code used is a binary Goppa code, but there are attempts to use other families, which are not yet broken).
So my question is, do we really need to reveal which family of code was used? wouldn't be more secure if we keep it hidden?

But the matrix is permuted, which is the operation enabling the trapdoor to operate.

Thus, the permuted matrix 'hides' the actual matrix $G$. So your extra hiding is unnecessary. The attacker knows the set of permuted generator matrices, but not the actual matrix.

The dimensions are huge, as a comparison, say you know that an RSA asymmetric key of 4096 bits has 2098 1's but nothing else.
That is a set of size $$\binom{4096}{2098}\approx 2^{0.999570 \times 4096}=2^{4094.23}$$ which is somewhat smaller than $2^{4096}$ but not by a significant multiplicative factor (less tha 2 bits weaker).

Knowing the code (say Goppa) and its parameters is important since these determine the strength implied by the length, dimension, and minimum distance of the code.

You could randomly choose a code, but then the advantage the legitimate decoder has, in terms of efficient decoding when in posession of $P,G$ and $S$ disappears.


What is the SSL private key file format? I was researching about how to encrypt with RSA. I understood everything but not the format of the private keys.

In the phpseclib (RSA in PHP), you can import your private key (private.key format) and in the key file there is text like this:

-----BEGIN RSA PRIVATE KEY-----
MIIBOQIBAAJBAIOLepgdqXrM07O4dV/nJ5gSA12jcjBeBXK5mZO7Gc778HuvhJi+
RvqhSi82EuN9sHPx1iQqaCuXuS1vpuqvYiUCAwEAAQJATRDbCuFd2EbFxGXNxhjL
loj/Fc3a6UE8GeFoeydDUIJjWifbCAQsptSPIT5vhcudZgWEMDSXrIn79nXvyPy5
BQIhAPU+XwrLGy0Hd4Roug+9IRMrlu0gtSvTJRWQ/b7m0fbfAiEAiVB7bUMynZf4
SwVJ8NAF4AikBmYxOJPUxnPjEp8D23sCIA3ZcNqWL7myQ0CZ/W/oGVcQzhwkDbck
3GJEZuAB/vd3AiASmnvOZs9BuKgkCdhlrtlM6/7E+y1p++VU6bh2+mI8ZwIgf4Qh
u+zYCJfIjtJJpH1lHZW+A60iThKtezaCk7FiAC4=
-----END RSA PRIVATE KEY-----

But when I decode this with Base64 and then convert it to decimal it is just one number...
I thought you need both $p$ and $q$! My question:

If I roll a dice (with 0 and 1) 1024 times and find the nearest prime number it would be my $p$ and I would do this process again so I get $q$, but how do I convert those numbers to the private.key format? And what's the difference?

Copy / paste that key into http://phpseclib.sourceforge.net/x509/asn1parse.php and you'll see that there are several different integers in there. $p$ is there, $q$ is there as is the exponent and several other integers to speed things up by taking advantage of the Chinese Remainder Theorem.
The key is encoded using DER and derives semantic meaning via ASN.1. The following URL elaborates:
https://datatracker.ietf.org/doc/html/rfc8017#appendix-C
Quoting I understand the mathematics of RSA encryption: How are the files in ~/.ssh related to the theory?:

The ASN.1 syntax for that DER-encoded string is described in
RFC8017 (aka PKCS1):
  Version ::= INTEGER { two-prime(0), multi(1) }
      (CONSTRAINED BY
      {-- version must be multi if otherPrimeInfos present --})

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

DER encoding uses a tag-length-value notation. So here's a sample
private key:
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----

Here's the hex encoding:
3082025c02010002818100aa18aba43b50deef38598faf87d2ab634e4571c130a9bca7b878267414
faab8b471bd8965f5c9fc3818485eaf529c26246f3055064a8de19c8c338be5496cbaeb059dc0b35
8143b44a35449eb264113121a455bd7fde3fac919e94b56fb9bb4f651cdb23ead439d6cd523eb081
91e75b35fd13a7419b3090f24787bd4f4e196702030100010281801628e4a39ebea86c8df0cd1157
2691017cfefb14ea1c12e1dedc7856032dad0f961200a38684f0a36dca30102e2464989d19a80593
3794c7d329ebc890089d3c4c6f602766e5d62add74e82e490bbf92f6a482153853031be2844a7005
57b97673e727cd1316d3e6fa7fc991d4227366ec552cbe90d367ef2e2e79fe66d26311024100de03
0e9f8884171ae90123878c659b789ec732da8d762b26277abdd5a68784f8da76abe677a6f00c77f6
8dcd0fd6f56688f8d45f731509ae67cfc081a6eb78a5024100c422f91d06f66d0af8072a2b70c5a6
fe110fd8c67344e57bdf2178d613ec442f66eba2ab85e3bd1cf4c9ba8dfff6ce69faca86c4e9452f
4343b784a4a2c8e01b0240164972475b99ff03c98e3eb5d5c741733b653ddaa8c6cb101a787ce41c
c28ffbb75aa069136be3bf2cafc88e645face4ed2d258cab6dda39f2dbed3456c05ead0241009182
d4c8393b2768e4dc03e818913ab3f11a8d9ba536eefdf86b4fc79b1e44f3d9ea6553d55041243363
5a193155fc8b59b95944cb3f3db22c9201415757aa13024011a88ae4a84a369f52157b8b57041a96
fcf21e4d058673597199dfbb09e50b16fac272a0d75edf11fcbdd5e1cd4ede4fcd83e97fec730f51
673fbfeab089e29d

The 30 is because it's a SEQUENCE tag. The 82025c represents the
length. The first byte means the length is of the "long form" (82 & 80) and that
the next two bytes represent the length (82 & 7F). So the actual length of the
SEQUENCE is 025c. So after that is the value.
Then you get to the version. 02 is of type int, 01 is the tag length
and 00 is the value. ie. it's a two-prime key as opposed to a
multi-prime key.
More info on the Distinguished Encoding Rules.
Trying to understand ASN.1 is a lot more complicated and a lot of it,
for the purpose of understanding the formatting of RSA private keys,
is unnecessary. For X.509 it becomes more necessary but RSA keys
aren't nearly as complicated, formatting-wise, as X.509 certs.
Hope that helps!


Is this hypothetical key-exchange secure? I've thought about the following (generic) key-agreement protocol.
The only weaknesses I could have found are missing freshness guaranteees.

As for the notions:
$E^1_K(P)$ is the symmetric encryption of plaintext $P$ using key $K$. This is AES-GCM for example.
$E^2_A(P)$ can either denote symmetric encryption (e.g. AES-GCM) of $P$ using the (pre-shared) key of $A$ or it can denote asymmetric encryption of $P$ using the public key of $A$, the scheme is for example ECIES or RSA-OAEP. Certificates must be provided in the first two steps if asymmetric encryption is used.
$k$ is a random 128/256 bit AES key which is chosen by A prior to the first message and not disclosed until message 3.

$A\rightarrow B:E_k^1(R)$
$B\rightarrow A:E_A^2(S)$
$A\rightarrow B:E_B^2(k)$

The derived key is $MS=H(R||S)$ with $H$ being a KBKDF. $R$ and $S$ are 128 to 256 bit secure random values, generated by a CSPRNG.

Now for the aims of the protocol:

Provide mutual authentication of both entities
Provide a new secure shared key, unknown to any third party
Disable any party to manipulate the derived key to have some special property

A quick design rationale:
The first message ensures that assumption (3) is hold, B can't choose his random value dependant on As and A can't change it. The symmetric / asymmetric encryption should ensure (2). The usage of IND-CCA2 / AEAD primitives should ensure (3) as well. The usage of the PSK / certificates should ensure (1), as only they can successfully authenticate the messages.

I know, nothing is secure without a formal proof.

So my question:
Is the above protocol likely to be secure?

By the way: The protocol won't be deployed. This is a question about (general) protocol design.

This is exactly where automatic protocol analysis tools can help you. For example, using the Scyther tool, the protocol description using symmetric encryption is:

/*
 * Protocol description for Scyther
 *
 * Note we use 'K' to model 'k' since Scyther assumes 'k(.,.)' refers
 * to pre-shared keys between two agents.
 */

// The protocol description with E^2 instantiated as symmetric
// encryption

hashfunction H;

macro msg1 = { R }K ;
macro msg2 = { S }k(A,B) ;
macro msg3 = { K }k(A,B) ;
macro sessionkey = H(R,S);

protocol testSymmetric(A,B)
{
    role A
    {
        fresh R: Nonce;
        fresh K: Nonce;
        var S: Nonce;

        send_1(A,B, msg1 );
        recv_2(B,A, msg2 );
        claim(A,Running,B,R,S);
        send_3(A,B, msg3 );

        claim(A,Secret,sessionkey);
        claim(A,Alive);
        claim(A,Weakagree);
        claim(A,Commit,B,R,S);
        claim(A,Niagree);
    }

    role B
    {
        var R: Nonce;
        var K: Nonce;
        fresh S: Nonce;

        recv_1(A,B, msg1 );
        claim(B,Running,A,R,S);
        send_2(B,A, msg2 );
        recv_3(A,B, msg3 );

        claim(B,Secret,sessionkey);
        claim(B,Alive);
        claim(B,Weakagree);
        claim(B,Commit,A,R,S);
        claim(B,Niagree);
    }
}

If you run this through the Scyther tool, you will find the key is secret, but agreement fails: an attacker can, for example, replace the random value in the first message by anything, causing B never to compute the key, but A still finishes and might think B now agrees on the values.
Thus, the protocol does not give you any decent authentication, but the partner is supposedly alive. This is what Scyther shows you:

If you modify the message macros for the asymmetric version, i.e.,

macro msg1 = { R }K ;
macro msg2 = { S }pk(A) ;
macro msg3 = { K }pk(B) ;

then the situation is much worse. Although the key is still secret, even the most basic authentication notion fails: along the lines of the previous attack, the attacker can complete a run with B without A ever being present.
A slightly more interesting attack is one on the A role (where the intended partner Bob is never alive):

In this case, the attacker just reroutes the messages and A thinks B is alive but completed the protocol with Charlie.

If you use the compromising adversaries version of Scyther you can also analyse KCI, UKS, and (w)PFS attacks, which will probably yield interesting results.


How can complexity be increased or decreased in AES? I have been studying data compression for a while. For educational purposes, after a lot of reading, I managed to create a software that performs encryption and authentication using AES256-GCM. However, I have now reached a point after which I cannot find a possible answer and this is confusing me.

My software allows the user to choose the "hardness" of the encryption, a value ranging from 0% to 100% (a scale). Nonetheless, I have not managed exactly how I could mingle the logic of "hardness" with the logic of AES. Yes, I have a lot of ideas about playing with the key, the IV, the resulting data and so on, but a point I have learned on this area is that you should never reinventing the well when there is already studies on the same aspects and whose results had been checked and rechecked over and over and over again.

Therefore, what would be the best way to perform such work? I seek for theory, not necessarily coding.

This begs the question, why would you in any real-world circumstance wish to reduce the difficulty for an attacker to break your cryptosystem?

To answer your question practically, the only reasonable way I can think of to accomplish this is to simply reduce the entropy in the key. At 100%, all 128 bits of the key are used. At 50%, 64 bits of the key are used, and the rest set to some static value (e.g., 0). At 25%, 32 bits of the key are used, and so on.

That said, I want to reiterate that there is no reason I can possibly conceive of to support such a feature, outside of sheer curiosity.

Edit: Note that this will result in an exponential decrease in security, which maps well onto how cryptographers typically think of the security of a system. Modern ciphers like AES-128 so strong that a 100-fold reduction in difficulty to break still leaves brute force well outside the realm of conceivable human feasibility ($\frac{2^{128}}{10^{2}} \equiv 2^{121}$).


What would be the best plain text Cryptography method without the use of a computer? What would be the best Cryptography method without the use of a computer?

  This could be a list of the current options available, that could be used without
  the use of a computer system/electronic device. Moreover, would like to identify what types of Cryptography techniques could be used to encrypt a small a amount of hand written, "plain text" without numbers or symbols just (characters). that being hard to implement or easy to implement.

Would like A brief description of:

E.g. types of cipher's
Different types of algorithm.
The range in security, low to high etc.

For confidentiality purposes?

one time pad (when possible)
rc4 (because you can by hand)


Why is XEX not used instead of CTR? As far as I know the only disadvantage that XEX has when compared to CTR is that you need a block cipher/permutation while CTR is fine with just a hash function. Meanwhile XEX offers the advantage that it is more misuse-resistant (reuse of the counter/nonce breaks CTR but this is not an issue with XEX) and less malleabile. Considering that, why is XEX almost never used outside of disk encryption?

If CPA-security is sufficient, then CTR is sufficient. If you need authenticated encryption (or CCA), then neither XEX/XTS nor CTR is sufficient and you should be using AES-GCM or something similar. In general, as soon as you want something that is "less malleable" then you consider malleability a threat and you should be using authenticated encryption. If you are worried about nonce misuse resistance, then likewise you should be using such a scheme (SIV or GCM-SIV, etc.).

There is just no good reason to use XEX/XTS, except when you have a severe limitation like in disk encryption that you cannot increase the sector size.


For ElGamal-based key encapsulation, is it necessary to hash before using as AES key? I'm working with SJCL, specifically using ElGamal to encrypt messages. Behind the scenes, this is doing something similar to what's described in this SO post (emphasis mine):

  Regardless how big prime p is, you can always generate a random m
  number in the range of 1 to p-1 and use that to produce your
  asymmetric ciphertext. Afterwards, you can take the previously
  generated m, encode it into a byte array (use toString(16) to produce
  a Hex-encoded string and then simply parse it as Hex for the hashing)
  and hash it with a cryptographic hash function such as SHA-256 to get
  your AES key. Then you can use the AES key to encrypt the message with
  a symmetric scheme like AES-GCM. This is called key encapsulation.

Here is the actual function:

kem: function(paranoia) {
    var sec = sjcl.bn.random(this._curve.r, paranoia),
        tag = this._curve.G.mult(sec).toBits(),
        key = sjcl.hash.sha256.hash(this._point.mult(sec).toBits());
    return { key: key, tag: tag };
  }

My question is: regarding key = sjcl.hash.sha256.hash(this._point.mult(sec).toBits()), is it necessary to compute SHA256 hash and use that as AES secret? Or can we get by with something like this: key = this._point.mult(sec).toBits() (no hash)? Would this be less secure?

I ask as I am trying to take advantage of multiplicative homomorphism of ElGamal. So, multiply encrypted secret by a scalar, decrypt new ciphertext, and multiply decryption result by scalar inverse to get original secret. I am able to do this when I remove the SHA256 hashing code above, however with hashing code still enabled I am getting a not on the curve error when trying to multiply decryption result by scalar inverse (because we are using hash for key which I believe pushes it off the curve).

So, wondering if removing hash logic degrades security of the method / is not advised or if hashing is performed for different reasons (and wondering what those reasons are if so).

The issue here was that the hashing is used to derive an AES key for encryption from the value $m$ in the question. However, it is still the value of $m$ that needs to be encrypted using the public key and the homomorphic ElGamal algorithm, not $H(m)$. After homomorphic decryption the value $m'$ can be retrieved, and $H(m')$ will create the same AES key to be used to decrypt the message iff $m' = m$.

The idea of the hash is to compress the entropy in $m$ so that the (leftmost bytes) of the result can be used as a well distributed AES key.

Even more information and the road towards this answer can be found in the comments below the question and the chat.


Why are there no MACs inspired by block cipher modes other than CBC and CFB? I've been studying message authentication codes and I was wondering why a MAC can only be produced with AES in CBC and CFB mode and why not the other modes such as ECB, OFB and counter.

Why are CBC and CFB suitable modes to produce MACs? Is there a certain trait that makes them special when compared to the other modes?

It is certainly wrong to state that "MAC can only be produced with AES in CBC and CFB mode", but there seems to be a simple reason that people were inspired by these modes when thinking up possible MAC constructions: They carry along some state that incorporates information from the message while traversing the input blocks. In both modes, encrypting a block involves taking the current state along with a message block and transforming them in some way to obtain a ciphertext block and an updated state. This is not the case with the other common block cipher modes.

ECB is completely stateless.
Counter mode (CTR) has some state (namely, the counter), but it is independent of the message and therefore useless to assert message integrity.
Output feedback mode (OFB) is also stateful, but the message is XORed into the to-be ciphertext block after the fed-back block has been tapped. Therefore, the state is independent of the message, just like for counter mode.


Reverse MD5 of a 76 character string when the first 44 characters are known I have a situation where I would like to reverse a hash which is the MD5 of a concatenation of 76 characters. I know the first 44 characters but don't know the remaining 32 characters. A description of the problem is as follows:

Hash = MD5 (cat (known_string_of_length_44chars, unknown_string_of_length_32chars))

I can generate Hash values for multiple combinations of the known_string. I would like to determine the unknown_string. Can this be done? Is brute forcing a possibility?

You have two problems, the first is the computational complexity of preimage attack on MD5. It is currently around 2^123 Pre-image attack on MD5 hash
This is technically better than brute force but way outside what is feasible in the forseeabile future.
But perhaps worse than that is the information theory limit. A preimage attack will find a pre-image, not the pre-image which was originally used. With 32 chars you get a space of 256 bi,  far more than 128 bits of MD5. This means there are expected to be many preimages of the required form.
This means if you want to find the original as opposed to just any value with the correct form and correct hash it is impossible even with infinite computing power.
The same thing also shows us that requiring a pre image of such a form can't improve the pre image attack complexity as we could have picked any prefix and still expect many solutions.
If you could have limited to a small preimage space you could brute force it. And if the space had some special form  the knowledge that a solution of a special form exist could theoretically make the attack even faster.


merkle tree motivation Here author seems to give overview of merkle trees.

However, I have one problem.

As in the article author claims you can use merkle trees to verify authenticity of data, e.g. if piece of data is authentic.

But I could use a simple hash of the file (signed), for authenticating/checking integrity of file too, right?

Why employ merkle trees for this purpose?
So it seems I am clearly missing something. Can someone enlighten me on this?

Usually you'd use one hash per file yes, but often torrents consist of multiple files. So you'd have a hash per file and possibly a top level hash to make sure that all the files are present. This way you can validate each file after it is downloaded; downloading and hashing can be performed in any order and in parallel - e.g. from within their own threads.

In principle you could also split the file in sections and hash those separately / in parallel. But with the speed of most hash algorithms this doesn't make much sense. And for integrity you're probably better off using e.g. PAR2 which provides error correction on top of error detection.

As for the authenticity: either the Merkle tree can be loaded from a secure location or the root may be signed, to name two common methods. So yes, you can use a Merkle tree to authenticate data, but you must be able to trust the tree itself first.


Could a crypto system that uses non-FIPS crypto but then upgrades complete to FIPS be FIPS certified? I know most people around here (including myself) are anti-FIPS, but I have a FIPS related question.

Could a crypto system that is not FIPS, e.g. one based on primitives like Curve25519, achieve FIPS compliance if it is capable of upgrading to FIPS algorithms/implementations in a way that is complete. By complete I mean in the upgraded mode it is using only FIPS compliant crypto and the upgrade occurs in such a way that all the previous security guarantees are re-confirmed using FIPS crypto.

Or would the mere presence of non-FIPS crypto at any stage of the system invalidate it for FIPS certification?

Yes, a device that is FIPS certified need not be restricted to using only FIPS-approved algorithms.  For example, in your case, FIPS has no problems with you supporting Curve25519, as long as the user can turn it off.  That is, the device will need to be able to be set in a mode that it performs only FIPS approved algorithms (and the FIPS approval documentation will have to explain precisely how to do that).

You specifically asked about 'crypto system'; if you're asking about a protocol, a protocol is not FIPS approved; FIPS approved devices, not protocols.


Verifying multiplicative inverse on a prime field in NIST's ECDSA_Prime.pdf I am trying to learn about the Elliptic Curve Digital Signature Algorithm (ECDSA) by verifying the results in some example calculations.  I found a PDF of example ECDSA calculations from NIST here:
http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ECDSA_Prime.pdf

In the section "Example of ECDSA with P-256", NIST gives two large hex numbers K and Kinv, which I presume are multiplicative inverses of eachother in the prime field of the P-256 curve.  I tried to verify that K * Kinv is equal to 1 (in modulo arithmetic) but I was unable to; I got a really large number instead of 1.

Could someone check my relatively simple work and tell me what I am doing wrong?  Or could someone verify it in their own way and tell me how they verified it?

Here is the excerpt from ECDSA_Prime.pdf I am looking at:

==============================================================
Signature Generation
msg is "Example of ECDSA with P-256"
Hash length = 256
...
K is
7A1A7E52 797FC8CA
AA435D2A 4DACE391 58504BF2 04FBE19F 14DBB427 FAEE50AE
...
Kinv is
62159E5B A9E712FB
098CCE8F E20F1BED 8346554E 98EF3C7C 1FC3332B A67D87EF

I found the prime value $p$ that defines the field for curve P-256 in NISTReCur.pdf.  I multiplied K and Kinv together in Ruby, taking advantage of that language's automatic handling of very large integers.  Here is my Ruby code:

# From http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
# in the section entitled "P-256"
nist_p = 11579208921035624876269744694940757353008614_3415290314195533631308867097853951

# From http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ECDSA_Prime.pdf
# in the section entitled "Example of ECDSA with P-256"
nist_k = 0x7A1A7E52_797FC8CA_AA435D2A_4DACE391_58504BF2_04FBE19F_14DBB427_FAEE50AE
nist_kinv = 0x62159E5B_A9E712FB_098CCE8F_E20F1BED_8346554E_98EF3C7C_1FC3332B_A67D87EF

puts (nist_k * nist_kinv) % nist_p    # expect to get 1, but did not

Note that the underscores are just spacers between the digits to make these long numbers more readable; they can be removed without affecting the program.

This code outputs the following number, even though I would expect it to output 1:

44876559229634927483363577082941808653359045812660811236387870057706848524951

I tried reversing the order of bytes in the NIST hex numbers and I also tried reversing the order of the 32-bit chunks, but neither yielded the correct result.

What am I doing wrong here?  Am I using the wrong value of $p$ for the P-256 curve?  Is my understanding of Kinv incorrect?  Did NIST miscalculate Kinv?

You are using the wrong value as the modulus; you ought to be using the value $r$ (which is also listed in the document).

$p$ is the characteristic of the field that the elliptic curve you're using is defined on.  In this case, we're not interested in that; instead what we're interested in is the order of the curve, that is, that value $r$ such that $rP = 0$ for all points $P$ on the curve (note: strictly speaking, we're interested in the order of the generator point, however in this case, that's the same).  That value $r$ is as listed.

$K$ and $K_{inv}$ are not inverses modulo $p$; instead, $K \times K_{inv} = 1 \ (\bmod \ r)$


Is it secure to use hexadecimal data for IV instead of raw binary? Is it safe and secure to use a function like bin2hex (which converts binary data to hexadecimal) on the binary output of functions like openssl_random_pseudo_bytes and mcrypt_create_iv?

Meaning: can I use the hexadecimal output instead of the raw binary data, or is there some kind of security risk involved when doing so?

An initialization vector is, in fact, always binary.  It's just random bits.  So, if you choose to encode those bits as a hexadecimal string for ease of storage or transportation, that is fine.  However, since it is the binary that is the IV, you will need to decode it back from hexadecimal to a binary value before using it in the decryption process.

As a note, you would certainly not want to use the binary values of the individual characters in a hexadecimal string as an IV, as that would limit you to a tiny set of possible IVs, much smaller than the space you need to generate IVs securely.


CPA distinguisher for matrix multiplication in GF(256) with randomized padding What is the best CPA distinguisher for the function $F_k:\{0,1\}^{8n}\to\{0,1\}^{16n}$ described below?

Let $E_k$ be a $2n\times2n$ matrix with elements in $GF(2^8)$, selected by generating bit strings of length $32n^2$ using a predefined function $PRF_k$, until one is found that is invertible e.g. using Gaussian elimination.

To encode an input bit string $M$, generate random bit string $Pad$ of length $8n$. Let the $2n$ element vector $T$ correspond to the concatenation $M|Pad$. Calculate the vector $C$ using the formula $E_kT^T=C^T$.

The decoding function is given by the $n\times2n$ matrix corresponding to the first $n$ rows of $E_k^{-1}$.

Obviously, you need no more than $4n$ chosen cipher texts and access to a decryption oracle, to be able to derive the decoding matrix. But is there a better CPA distinguisher than statistical analysis of the skew caused by a constant $M$ for a relatively large number of $Pad$ values?

While Ilmari answered the specific question you asked (Chosen Plaintext Distinguishers), I would like to note that the attack can be sharpened into a Known Plaintext Key Recovery attack (where, by key recovery, I don't mean recovering the $E_k$ matrix, but instead allowing an attacker to reconstruct enough information to decrypt arbitrary texts).

One straightforward way to see this is to observe that the decryption process is entirely linear; that is, if we know that:

$Decrypt(C_1) = P_1$ and $Decrypt(C_2) = P_2$

then

$Decrypt(aC_1 + bC_2) = aP_1 + bP_2$  for $a, b \in GF(2^8)$

So, all the attacker needs to do is collect $2n$ linearly independent ciphertexts with corresponding known plaintexts:

$Decrypt(C_1) = P_1$

$Decrypt(C_2) = P_2$

...

$Decrypt(C_{2n}) = P_{2n}$

Then, do decrypt an arbitrary ciphertext $C_x$, he solves the linear equation for $a_1, a_2, \ldots a_{2n}$:

$C_x = \sum_i a_i C_i$

and then he knows that

$Decrypt(C_x) = Decrypt( \sum_i a_i C_i) = \sum_i a_i P_i$


Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree? One of the problems of one-time Lamport signatures is that public keys are disposed after use, so you must generate many keys and store them in a Merkle tree. The root is the "real" public key and each signature is supplied with a Merkle branch from the root public-key to the one-time public key.

I was thinking of using a cryptographic accumulator to store efficiently the one-time public keys. The root public-key would be the the digest of accumulated one-time public-keys. A signature would only include the proof that the one-time public key belongs to the accumulator. This proof may be shorter than a Merkle branch if the number of public keys is over 256, for comparable security thresholds.

The only drawback I see is that known cryptographic accumulators (e.g. Benaloh and M. de Mare) are based on number-theoretic assumptions (such as factoring), and using Lamport signatures one is usually trying to avoid those assumptions, probably to get quantum computing resistant schemes.

Nevertheless, I suspect there are cryptographic accumulators which are quantum computing resistant, so the argument may not be strong enough.

To summarize, may cryptographic accumulators serve as a more efficient method to distribute Lamport public keys ?

Yes, they can be used for that purpose.  The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures.  Nonetheless, they can be used in this way.


Given a prime exponent e and a prime number n, find b, where b^e = 1 mod n Can anyone help me with the following problem.
Given  a prime exponent $e$ and a prime number $n$, find $b$, where  $b^e \equiv 1 \bmod n \land b > 1$. For example, $b^5 \equiv 1 \bmod 11$ how to find $b$ ?
Can anyone describe me the steps please.

If $n$ is prime, $\mathbb{Z}_n^{*}$ has a primitive root $g$ and order $n-1$. So if $e$ divides $n-1$ you have $(g^{\frac{n-1}{e}})^e=1$.
For $n=11$ you  have e.g. the primitive root $g=2$ and therefore with $$b\equiv 2^{10/5}\equiv 2^2 \equiv 4 \pmod {11}$$ you compute $$b^5 \equiv 4^5 \equiv 1024 \equiv 1 \pmod {11}.$$

With the remaining primitive roots $g=6,7,8$ you get other solutions
$b\equiv 6^2 \equiv 3 \pmod {11},$  $b\equiv 7^2 \equiv 5 \pmod {11},$
and $b\equiv 8^2 \equiv 9 \pmod {11}.$

But be aware that your problem may have no solution: in your example there is no $b\not \equiv 1$ with $b^3\equiv 1 \pmod {11}!$


Is the any QR code with built-in hash of the information? For example, the text is something like

"Hello world!"

And after that text should be new line with hash (sha256):

9e77bdb7b7b67bee57fe10946ac0275e38585c688ace439d96d82ebf71c26496

So, now it is not possible to modify QR code (recoloring some squares) without loosing it.

Is something like this implemented for QR coding outside, where it is possible to modify the code?

There are encrypted QR codes from DENSO ADC.  I know that these can be encrypted or just signed; however, DENSO ADC has never been forthcoming with how they work.  They seem to work by putting data after the "data section" of the QR code that would otherwise be ignored.  If you were going to have something similar, I would take that approach.


Asymmetric Encryption vs Shared secret via ECDH I'm reading RFC8291. Here's a figure on how Web Push Notifications work in general:
    +-------+           +--------------+       +-------------+
    |  UA   |           | Push Service |       | Application |
    +-------+           +--------------+       +-------------+
        |                      |                      |
        |        Setup         |                      |
        |<====================>|                      |
        |           Provide Subscription              |
        |-------------------------------------------->|
        |                      |                      |
        :                      :                      :
        |                      |     Push Message     |
        |    Push Message      |<---------------------|
        |<---------------------|                      |
        |                      |                      |

                                 Figure 1

Then, RFC8291 adds cryptography on top of it. If I understood correctly:

In the "Provide Subscription" step, the User Agent (UA) and the Application both agree on a shared secret using ECDH.
Then, when the Application wants to send a push notification to the UA, it encrypts symmetrically (via AES) the notification content using the shared secret.
The Push Service relays this encrypted notification to the UA.
The UA decrypts the notification content using the shared secret.

My question is: why use ECDH when simple asymmetric encryption/decryption can be used?

UA generates a private/public key pair.
In the "Provide Subscription" step, the UA sends its public key to the Application.
The Application, when it wants to send a push notification, encrypts the notification content with UA's public key.
Same as before, the Push Service, relays the encrypted message.
The UA decrypts the encrypted notification content with its private key.

What are the trade-offs between the method I described here, and the one in the RFC?

Your alternate method has an expensive public key operation for each push message.
While the first protocol does a key exchange just once per subscription and then continues with a symmetric key.
If in the key exchange both sides authenticated themselves (Or at least the Application) the user can rely on this, if authenticated encryption is used it still a fast symmetric key operation to decrypt and authenticate the message.


What is the sign bit for in Feige-Fiat-Shamir? The Feige-Fiat-Shamir identity scheme is based on a ZKP assuming that square roots are "hard" modulo an integer of unknown factorization.  The "parallel version" of this protocol includes a "sign bit" and the wikipedia article claims that the older version of the protocol leaked a bit, so the sign bit was added.  Here is the protocol as given by wikipedia:

Peggy chooses a random integer $r$, a random sign $s\in\{-1,1\}$ and computes $x \equiv s\cdot r^2 \pmod{n}$. Peggy sends $x$ to Victor.
Victor chooses numbers $a_1, \cdots, a_k$ where $a_i$ equals 0 or 1. Victor sends these numbers to Peggy.
Peggy computes $y \equiv rs_1^{a_1}s_2^{a_2} \cdots s_k^{a_k}\pmod{n}$. Peggy sends this number to Victor.
Victor checks that $y^2 \equiv \pm\, x v_1^{a_1}v_2^{a_2} \cdots v_k^{a_k}\pmod{n}$.

I cannot find the old version of FFS, nor do I see what bit is leaked without the sign bit added.  It must be something related to a Jacobi symbol?!

The relevant quote from Wikipedia that I'm asking about is:

  In an early version, the Fiat-Shamir-Scheme (on which the
  Feige-Fiat-Shamir-Scheme was based), one bit of information was
  leaked. By the introduction of the sign s even this bit was concealed
  resulting in a zero-knowledge-protocol.

So if this sign value $s$ were removed, what would be leaked?

Note: After reading Samuel's response, I wonder if the wikipedia version of the scheme is actually correct?!

The original 1986 Fiat-Shamir paper can be found here. The subsequent Feige-Fiat-Shamir 1988 paper can be found here, and contains the answer (Section 3):

  The $S_j$ (which are witnesses to the quadratic residuosity character of the $I_j$) are effectively hidden by the
  difficulty of extracting square roots $\bmod n$, and thus A
  can establish his identity by proving that he knows these
  $S_j$. By allowing $I_j$ to be either plus or minus a square
  modulo a Blum integer, we make sure that $I_j$ can range
  over all the numbers with Jacobi symbol $+1 \bmod n$ and
  thus the $S_j$ exist (from B’s point of view) regardless of
  $I_j$’s character, as required in zero knowledge proofs of
  knowledge.


Finite fields and ECC I understand modular arithmetic(or at least I think I do!) and I've tried to read and learn about how the Math in RSA works(and I think it went pretty well). I've been reading up on ECC and it looks very interesting and I tried solving a few basic math problems that involve ECC. I understand the basics, now I'm trying to understand it on a deeper level.

I find it easier to learn where I have analogies so my understanding stands as follows at this point — ECC is not a cryptosystem as such, it is a technique, much similar to the concept of using primes in RSA. Using ECC, encryption algorithms such as El-Gamal and signing algorithms such as ECDSA can be implemented.

I understand the properties about what a group, field are : However I see this statement in quite a few places. My doubts are as follows:

What does it mean to say “E is an elliptic curve over $\mathbb{F}_p$, where $p$ is prime"?
Does the cardinality of a curve mean the number of primes that are on a curve?
How does real-world ECC encryption work? In a problem I had tried solving, the message was denoted as a point on the curve. However, I imagine that its infeasible/impractical to always be able to denote messages as a point on the curve.
Any additional reading resource suggestions would be awesome!

When an elliptic curve is said to be "over a field $K$", we mean that the curve is the set of "points" $(x,y)$, where both $x$ and $y$ are elements of $K$, such that the curve equation is fulfilled. The curve equation may have various representation, but a typical one is $y^2 = x^3 + ax + b$ for two constants $a$ and $b$ which are also elements of $K$. An additional formal point, the "point at infinity" (denoted $\mathcal{O}$), which has no $x$ and $y$ coordinates, is also part of the curve.

In cryptography we are mostly interested in finite fields. A finite field is traditionally denoted $\mathbb{F}_q$ for some integer $q$, which is the size (cardinality) of the field; it so happens that when two finite fields have the same number of elements, they are isomorphic to each other, which more or less means that they have the same structure; morally, both are "the same" field, which is why we can afford to say "the field $\mathbb{F}_q$. There exists a finite field $\mathbb{F}_q$ if and only if $q = p^f$ for a prime $p$ and an integer $f\geq 1$. When $f = 1$, i.e. the field cardinality is a prime integer $p$, then the field $\mathbb{F}_p$ is (isomorphic to) the set of integers modulo $p$.

In a finite field $\mathbb{F}_q$, there are $q^2$ pairs $(x,y)$, so the curve cannot contain more than $q^2+1$ points (including the point at infinity), which means that the curve is also a finite set of points. The cardinality of the curve is its size: the number of points it contains (again, including the point at infinity). Actually, the curve cardinality is close to $q$: if we define $t$ such that the cardinality of the curve is equal to $q+1-t$, then it can be proven that $|t| \leq 2\sqrt{q}$ (that's Hasse's theorem).

Roughly speaking, for about half of the $q$ possible values $x$ in the field $\mathbb{F}_q$, there can exist a curve point $(x,y)$, and when there is one, there usually are two. The "two" and the "half" mostly cancel out, and you end up with about $q$ points on the curve.

For practical usage of elliptic curves, we use a conventional generator which is a point $G$ on the curve. That point has an order: the order $n$ of the point $G$ is the smallest integer $n \geq 1$ such that $nG = \mathcal{O}$. There are $n$ points $kG$, for all integers $k$ from $0$ to $n-1$, and these are, collectively, a subgroup of the curve. This implies that $n$ is a divisor of the curve cardinality. We usually look for curves and generators such that $n$ is a big enough prime; if possible, we arrange for the curve cardinality to be itself prime, and then $G$ generates the whole curve (in particular, any point on the curve, except $\mathcal{O}$, can be used as generator).

For real-world encryption on the curve, well, we do not really encrypt. We use Diffie-Hellman. The DH algorithm produces a shared secret value, which happens to be a curve point. The point selection is basically random, but a shared random value is good enough because it can be used as key (after a suitable hashing) for symmetric encryption. There is a name for that combination: ECIES. But some standards just do the DH and then use their own symmetric encryption system (typical of SSL/TLS with the "ECDHE" cipher suites).

ElGamal could also be used, but it would require mapping, in a reversible way, a "message" $m$ into a curve point. This would be interpreting the message as the coordinate $x$ (in $\mathbb{F}_q$) of a curve point, and computing a matching $y$. However, only about half of the $x$ values can be the first coordinate of a curve point, so some "variability" would be needed (some bits which can be adjusted until a possible $x$ is reached), or some other trick (e.g. not using one curve but two curves which complement each other). Since the size of the message $m$ would be severely limited (no bigger than $q$), this is hardly worthwhile, and nobody does that. People use Diffie-Hellman.

The guide to elliptic curve cryptography is a good reading for a practical view on how things are done. The chapter on finite fields can be downloaded for free, so I warmly encourage you to read it first.


Does SRP reduce to DH key exchange when shared password is not secret? I can find JavaScript implementations of SRP (Secure Remote Password protocol), but nothing that inspires confidence for Diffie-Hellmen key exchange. I also have a separate need for SRP later.

I would like to do key exchange under the assumption that I've already done mutual authentication (through some out of band user intervention). And I was wondering whether under these conditions I can use SRP with a non-secret password to do key exchange.

I would like to keep the client in JavaScript as simple as possible, and for SRP I only need a BigInt library, a hash function, and a cryptographically appropriate RNG. (DH wouldn't need the hash function, but I'll be needing SRP later for other stuff).

I'm trying to save myself the trouble of finding a good JavaScript implementation for DH or the danger of trying to write it myself.

The SRP paper has this point in its list of security properties:

    6. If the user's password itself is compromised, it should not allow the intruder to determine the session key K for past sessions and decrypt them. Even present sessions should at least be protected from passive eavesdropping.

The following section is titled Reduction to Diffie-Hellman and shows that, given an algorithm which retrieves the session key from the transmitted values and the password, you can also solve the computational Diffie-Hellman problem.

So yes, SRP is as secure as Diffie-Hellman for key exchange if the password is known to the attacker (and the other parameters are chosen properly, i.e. uniform random in their respective domains).

On the other hand, SRP with a non-secret password has the same problem as the pure Diffie-Hellman key exchange, when facing an active attack, i.e. a man-in-the-middle or an attacker who impersonates only one of the two parties.

  I would like to do key exchange under the assumption that I've already
  done mutual authentication (through some out of band user intervention).

Sorry, this rings alarm bells. Depending on how this out of band user intervention looks like, it could prove nothing at all about your actual communication going on, or about the non-existence of a man-in-the-middle attack.

Your "out of band authentication" should at least verify some value derived from the negotiated secret $K$, or (if you want it to go on beforehand) negotiate some (real) secret which then goes into the process as a part of the "password", so the attacker actually doesn't know the password, and can't mount a man-in-the-middle attack.

Also, as mentioned by CodesInChaos in a comment, SRP (as DH) does a lot of exponentiating of values by secret exponents. This is prone to timing and power analysis attacks if done naively, so your "default" JavaScript BigInteger implementation will have problems here.

If you want to run this in a Web browser (what JavaScript leads to believe), also take note that this will not more secure than the connection by which the browser got the code (hopefully at least an HTTPS connection), and good random numbers are a critical problem there. Also, side channel attacks are even easier if run on an untrusted platform like a web browser. More details in the article Javascript Cryptography Considered Harmful.


Why is RSA encryption significantly faster than decryption? I am designing an implementation of RSA . I recorded computation times in Java by using System.currentTimeMillis(). It returned an encryption time of 0.05 ms and decryption time of 0.55 ms, or a ratio of 1:11.

This seems like a large difference. Is it supposed to be this way?

//here my key has 256 bits
 for (;;) {
            long begin = System.currentTimeMillis();

            for (int i = 0; i < num; i++) {

            decrypt();
            }

            long end = System.currentTimeMillis();

            long time = end - begin;

            if (time >= 10000) {
                System.out.printf("Average Encryption takes: %.2f ms\n",
                        (double) time / num);
                break;
            }

            num *= 2;
        }

p = BigInteger.probablePrime(128, random);
q = BigInteger.probablePrime(128, random);
N=(p.subtract(one)).multiply(q.subtract(one));
e=BigInteger.probablePrime(32, random);
d=e.modInverse(N);
private void encrypt()
{

C= M.modPow(e,N);

}

private void decrypt()
{
    RM = C.modPow(d, N);
    }

Yes.  RSA encryption is faster than RSA decryption, assuming you choose the public exponent properly (e.g., you use $e=3$).

This is because raising something to the 3rd power (which is what you do during encryption) is much faster than raising something to the $d$th power, where $d$ is a 2048-bit number (as you do during decryption, assuming a 2048-bit modulus).

The Chinese Remainder Theorem can be used to speed up decryption, but only by a factor of up to $4\times$, which is not large enough to change the bottom-line conclusion.

You can test this for yourself by running openssl speed rsa2048 to test the speed of encryption and decryption using 2048-bit RSA.  On my machine, encryption is roughly $35\times$ faster than decryption.  Don't take this number too seriously -- the exact speedup factor will depend upon a number of factors -- but it demonstrates the bottom line, which is that in RSA, encryption is faster than decryption.