Security of a custom AES-based attack model Provided that:

$AES(plaintext, key)$ is the standard AES block cipher for a 128 bits block.
$\oplus$ is the standard XOR operation.
$K$ is a constant 128 bits pseudorandom value, which is used as the key for AES operations, unknown to the attacker.
$A$ is another constant 128 bits pseudorandom value, unknown to the attacker.
$B$ is a variable 128bits pseudorandom value, unknown to the attacker.
$C$ is a 128bits value which is known and can be chosen freely by the attacker.

An attacker can:

Obtain the value of $AES(A, K)$ (which is constant).
Obtain the value of $AES(B, K)$, for as many different $B$'s as he wants (note that the attacker cannot choose the value of $B$).
Test if $C = AES(A \oplus B, K)$; he can also obtain the value of $AES(B, K)$ being these 2 $B$'s the same value.

Can the attacker take advantage of this knowledge? For instance, could he guess a value for $C$ that is equal to $AES(A \oplus B, K)$, or recover $K$, $A$ or $B$?

I'm guessing from your description that you are describing a mode of operation where $A$ is the message and $B$ is an IV/nonce for a specific block. However you seem to have made an exception where the attacker can know the ciphertext both with and without the $B$ involved. As such, you have a rather weird use of the cipher. To generalize to an arbitrary block cipher:

$ENC(A, K)$ reveals the ECB mode ciphertext
$ENC(B, K)$ reveals the uniqueness of $B$
$ENC(A \oplus B, K)$ reveals the ciphertext using a proper mode of operation.

As such, you essentially have an overcomplicated ECB mode with random inputs. The value $B$ becomes irrelevant to an attacker knowing $ENC(A, K)$. If an attacker needs to find $B$, however they can use the same ECB breaking since they also know $ENC(B, K)$.
This system is strengthened by the fact that $A$ and $B$ are both pseudo-randomly generated (hopefully in a secure manner), and as such normal attempts to break ECB would be useless. Your system also is indistinguishable from random for any number of encrypted blocks, since your input is actually random.
With your system it is impossible, assuming you use a secure encryption algorithm (AES is generally accepted to be secure) to obtain any useful information about the inputs faster than brute-force, even with ECB mode; except in the case of repeating inputs, at which point statistical analysis becomes possible. But for random inputs no statistical analysis is possible.
The only issue I see with this model is the sketchiness of your system - why would your system ever need to reveal $ENC(A, K)$, $ENC(B, K)$ and $ENC(A \oplus B, K)$? I'll leave that for you to decide.
I'm thinking you mean a kind of OTP where $A$ and $K$ make a private key used to generate authentication codes verified by a server also knowing $A$ and $K$... It doesn't really matter, I'm just trying to see if I can guess your intentions.


Why do a pair of interactive machines have a common input? I know that an interactive proof system $(P,V)$ is a pair of interactive machines for a language $L$ if $V$ is polynomial-time and the following two conditions hold:

1) Completeness: For every $x \in L$,
$$\Pr [\langle P,V \rangle (x) = 1] \geq \frac{2}{3}$$

2) Soundness: For every $x \not\in L$ and every interactive machine $B$,
$$\Pr [\langle B,V \rangle (x) = 1] \leq \frac{1}{3}$$

Actually, in an interactive proof system $(P,V)$ for language $L$, $P$ proves the fact whether $x \in L$ to $V$.

However, for a general pair of interactive machines, what is the meaning of the common input? Can we construct a system $\langle A,B \rangle$ such that $A$ wants to send $x$ to $B$ and prove that $x$ is not malicious before sending it. Or can we construct other communication systems instead of a proof system?

Interactive Turing Machines are used to model real-world parties that interact and perform local computations using some algorithms. So, why would they not have a common input? The common input simply capture the fact that both parties can start a protocol knowing some common value, which perfectly makes sense in any real-life application. In the definition of interactive proof system, we want to abstract out what it means to interactively prove a statement; so, the natural approach is to let both parties initially know the statement, and ask for one of the parties to prove it to its opponent. The question of how the statement became known to the parties is irrelevant to the question of building an interactive proof.

That being said, yes, you can trivially let one of the parties send the statement to the other party, and then prove its truth with an interactive proof system. Depending of the specific interactive proof system you consider, some might not require knowing the actual statement during the interaction (although it will be clearly needed by the verifier when executing his verification algorithm on the transcript). In this case, the proof could indeed be performed first, and the actual statement be sent later. But that's not the case of all existing proof systems.


Hash functions with or without secret key The classical definition of hash functions (found in books) are OK, but when studying a little more there is a lot of notions that seem ambiguous (contradictory) to me :

Sometimes we have hash functions that need a secret key $k$
Certain papers that design hash functions speak about a family of hash functions, meaning I think, that there is a parameter $k$ that we choose at random to select a function among this family. We could think that this parameter is a secret key, or not, that is not clear for me...
Sometimes we have hash functions that doesn't need a secret key. Besides, if we consider a hash function like SHA-2, we don't need any secret key to use it,  nor we need to select such $k$ at random and I know that for any implementation SHA-2 gives the same result for the same input (this function is deterministic...)
I've read that a hash function that need a secret key is in fact a MAC. However, some papers that speak about a hash function needing a key doesn't say that this is in fact a MAC.

So, I have several questions:

When we want to use a particular collision-resistant hash function (in order to use it for a signature), from a specification of a hash function family, how I have to choose the parameter $k$ ?
Is a hash function that need a secret key necessarily a MAC ?
If not, is this kind of hash function usable like any other collision-free hash function ?  For using it in a signature (for example) ?

Thank you.

The parameter $k$ appeared in the definitions of hash functions, since many properties are difficult to formulate for a single concrete hash function. For instance, what would it mean that SHA-256 is collision resistant? Clearly, there are values that collide, and there exists a very short algorithm that outputs a collision in a small constant time. To meaningfully define collision resistance, theoreticians started talking about infinite families of hash functions
$$
H = \{H_k\,|\,k\in \mathbb{N}\},
$$
so that the family $H$ is collision resistant if an adversary needs to spend asymptotically $O(2^{n/2})$ time to find collisions for $n$-bit hash function from the family. Though the definition becomes sound, it does not help in practice since it is hard to expand the single SHA-256 to an infinite family of functions.

This parameter $k$, introduced solely to simplify the theory of hash functions, is often confused with a secret key. A hash function might take a key $K$ as an input, usually to form a message authentication code (MAC). A MAC should be difficult to forge, i.e. it is hard to find $M$ and tag $T$ such that
$$
H(K,M) = T
$$
without knowing $K$ (but knowing tags for other messages).

To answer your questions now

Whenever you need a collision-resistant hash function you choose a concrete function according to your security requirements and environment restrictions. You do not bother about families, they are for theoreticians.
It is usually MAC, but can also be a key derivation function. Usually MACs are not called hash functions (with key). When we talk about hash functions with key, it is quite often a usual hash function with part of its input made secret.


Significance of 3mod4 in squares and square roots mod n? Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?

If $p \equiv 3 \pmod{4}$ then $p + 1$ is divisible by 4. If we want to take the square root of $a$ mod $p$ then:

$$\left ( \pm a^{\frac{p + 1}{4}} \right)^2 \equiv a^{\frac{p + 1}{2}} \equiv a^{\frac{p - 1 + 2}{2}} \equiv a^{\frac{p - 1}{2} + 1} \equiv a^{\frac{p - 1}{2}} \cdot a \pmod{p}$$

But since $a$ was chosen to be a quadratic residue (otherwise it has no square roots) it follows that:
$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$
And hence the two square roots of $a$ modulo $p$ can in this case be very easily computed as:
$$\pm a^{\frac{p + 1}{4}}$$
Unlike the case for $p \equiv 1 \pmod{4}$ which requires more work to find the square roots of $a$ mod $p$. It is still possible, of course, just a bit more involved (e.g. see the Tonelli-Shanks algorithm).

So that could be one possibility. Another possibility is to observe that $p \equiv 3 \pmod{4}$ simply means that $p - 1$ is only divided once by 2, which might be a requirement or a desirable attribute in many contexts.


Is it possible to decrypt this message with partially known data? The following highlighted text must contains 547a5e0e008be33730158d63ce844e67 data. I don't know about encryption method and key.

Is it possible to decrypt it?

Or just give me some idea about encryption method that they use to encrypt it.

The first 32 bytes seem to be the ASCII representation of a 16-byte hexadecimal string. Possibly an Initialization Vector (IV) or similar. That would leave us with 88 bytes remaining. My guess is that this encryption is made by some 128-bit block cipher (e.g., AES-128), using some mode of operation such as CTR or CBC. Note that 88 bytes is not a valid ciphertext size when using AES-128 and CBC mode, but maybe there are 8 bytes that are not part of the ciphertext.

It would be nice if you provide a textual version of the highlighted hexadecimal data.


Differential trails in FEAL-8 In this paper the authors describe a differential attack against FEAL-8. They find several short differential trails, then extend the attack to the full 8-Rounds of the cipher by algebraic means.

In the diagram below, the differential trail includes a zero difference. How is this possible? If the inputs lead to a zero difference at some round in the middle of the cipher, would the intermediate ciphertexts not continue to stay the same for all future rounds?

How are these differential characteristics discovered? It seems easy to iterate over a (small) round function and find the difference probabilities for the inputs, but how can the authors see what the inputs are that cause the desired difference somewhere at a middle round of the cipher?

The difference values in the diagram denote the differences going into and coming out of the round function, which only operates on half of the state.  The differences of the two halves of the state are not shown after every round - you have to infer them from the 'omega' differences at the top and the output differences of the round functions.

Note that the difference going into the first round is 00 00 02 02x.  In a Feistel cipher, the input to the round function is a copy of one half of the state - the half that is not modified by the round function.  So that means after the first round, one half of the state still has that same difference (although at the end of the round that half of the state is swapped with the other half).

Now note that the output of the second round function is also 00 00 02 02x.  The output is xored with one half of the state, which is the same half that was copied and used as the input for the first round.  Since the differences are the same and xor is its own inverse, the two differences cancel out.  So now half of the state has difference zero.  The other half still has difference 00 80 02 82x.

The two halves are swapped again, and now the half with difference zero is used as the input for the round function.  But since an input with zero difference always generates an output with zero difference, the diagram shows zeroes in the inputs and outputs of the round function with probability 1.  Do note however that there is still an active difference in the whole state, just not in the half that was copied and used as the input to that third round.

In terms of your second question, these differences are discovered by carefully examining the round function - decomposing it into smaller functions (e.g. s-boxes), examining the difference distribution tables of those smaller functions, and watching how differences from the smaller functions interact in the whole round function.  For extending this over several rounds, attackers typically compile a list of the highest probability single round differentials, and then try to stitch together a high probability multi round characteristic from those.

For ciphers like FEAL, attackers generally look for high probability iterative characteristics, which are difference trails that stretch over a handful of rounds but which have the same initial and final states (just like in the diagram).  Such iterative characteristics enable the attacker to break many rounds, simply by repeating the characteristic as many times as necessary.


BLAKE2: What is the difference between the salt and the personalization? Libsodium builds their KDF on top of BLAKE2b:

BLAKE2B-subkeylen(key=key, message={}, salt=subkey_id || {0}, personal=ctx || {0})

Besides the key, the function has two additional arguments: The subkey ID (a 8 byte value which is 0-padded and becomes the salt) and a personalization context. They document those two values as follows:

  subkey_id can be any value up to (2^64)-1

And:

  Similar to a type, the context ctx is a 8 characters string describing what the key is going to be used for.
  Its purpose is to mitigate accidental bugs by separating domains. The same function used with the same key but in two distinct contexts is likely to generate two different outputs.
  Contexts don't have to be secret and can have a low entropy.

If I understand this correctly, both the 8-byte subkey ID (which becomes the 16-byte salt) and the 8-byte ctx (which becomes the 16-byte personalization) are used for "namespacing", don't have to be secret and may be of low entropy.

In BLAKE2b, what is the difference between the salt and the personalization context? Can the personalization context be considered the "second part of the salt", introduced only for semantic purposes? And if yes, wouldn't using a single 32-byte salt be simpler to understand and less error-prone to implement?

Context should be constant for one "keystore": that is the property of the KDF that is used for namespacing the salt space and make sure that two different application (or keystore) will not reuse the same salt.

Subkey_id, however, needs to be different for each key within a given key store and it is NOT to be used for namespacing. It can be constant for a given subkey ID though (even when the unhashed data changes).

The purpose if to make sure different applications can safely generate unique salt values without having to perform a full scan: all you need if for each app to have it's own context and then they can use a simple counter for subkey ID.


What is the complexity of the Square attack against the reduced 4-rounds 128-bit Rijndael variant? I'm looking at a square attack against a reduced version of AES-128 with only 4 rounds (with block and key size of each 128 bit). I have a set of 256 plaintext-ciphertext block pairs.

What is the complexity of the computations, in number of encryptions, partial encryptions, memory usage, and data requested?

There are two well-known distinguishers of reduced-rounds version of AES based on integral cryptanalysis. The first one is a 3-rounds distinguisher from Daemen and Rijmen while the other is a 4-rounds distinguisher from Gilbert and Minier.

The 3-rounds distinguisher relies on the fact that one byte $y$ of the state in the third round is the xor of four one-to-one mappings $z_i:x\mapsto z_i(x)$ from a given byte $x$ in the state of the first round, and therefore, on the property that $\sum_{x\in GF(2^8)} \left[z_1(x)+z_2(x)+z_3(x)+z_4(x)\right]$. Hence, the distinguisher requires $2^8$ (well crafted) plaintexts and as many encryptions, but basically no memory.

The 4-rounds distinguisher relies on the fact that the above-mentioned byte $z$ is actually a function of $x$ and three constants $c_1$, $c_2$, $c_3$ hereafter referred to as $c$ and the probability that there is an unusually high chance that the functions $z_{c'}$ and $z_{c''}$ are equal: this can be tested through the equality of the linear combination of four bytes resulting from the encryption of the two corresponding plaintext. The property is observable after browsing through $2^{16}$ values of $c$ (and enough of the possible values for $x$). Hence, the disinguisher requires about $2^{20}$ plaintexts and as many encryptions as well as less than $2^6$ bytes of memory.

These distinguishers are meant to be turned into key recovery attacks, but these extend to at least 6-rounds AES. Since you mentionned 4-rounds attacks without further details, I assume you referred to one of the above. If you need a more precise answer, you should refine your question. Also, make it precise which version of Rijndael you're referring to as it may impact the underlying complexity.


Clarification on Hill Cipher crib dragging technique --- this has been edited as I realised the question was silly. replaced with helpful information ---

I want to confirm the following:

Given ciphertext "AGHTDIX... [cont.]" (C)

and crib (a word which I know exists in the plaintext) "WITH" (P)

I am attempting to find the key (K) by shifting "WITH" one spot down the text each time like so:

A   G   H   T   D   I   X
W   I   T   H   .   .   .
.   .   .   .   .   .   .
.   .   W   I   T   H   .
.   .   .   .   .   .   .

And calculating it using the formula (multiply the ciphertext matrix by the modular inverse of the plaintext/crib - sorry, I don't know how to insert proper formulas here):

[K] = [C] x [P]-1 (mod 26)

My question -- was -- really silly as I forgot that the Hill cipher encrypts in pairs. Crib dragging should then adapt to include letters which could come before or after the known plaintext.

A   G   H   T   D   I   X
W   I   T   H   .   .   .
[?  W]  [I  T]  [H  ?]  .
.   .   W   I   T   H   .
.   .   .   .   .   .   .

Answer below explains in better detail. Thank you :)

I suppose (as you use a length $4$ crib) that your encryption matrix $C$ is of the form

$$\begin{bmatrix}
k_{11} & k_{12}\\
k_{21} & k_{22}\\
\end{bmatrix}$$

and so assuming word $(w_1, w_2, w_3, w_4)$ at a certain position $m$ gives two systems of equations $$\begin{bmatrix}
k_{11} & k_{12}\\
k_{21} & k_{22}\\
\end{bmatrix} \begin{bmatrix}
w_1\\
w_2\\
\end{bmatrix} = \begin{bmatrix}
c_m\\
c_{m+1}\\
\end{bmatrix}$$ and

$$\begin{bmatrix}
k_{11} & k_{12}\\
k_{21} & k_{22}\\
\end{bmatrix} \begin{bmatrix}
w_3\\
w_4\\
\end{bmatrix} = \begin{bmatrix}
c_{m+2}\\
c_{m+3}\\ \end{bmatrix}$$

which gives $4$ equations in the four key entries, rewritten as, e.g. $$
\begin{bmatrix}w_1 & w_2 \\
w_3 & w_4\\
\end{bmatrix} \begin{bmatrix} k_{11} \\ k_{12} \end{bmatrix}
= \begin{bmatrix}c_m \\ c_{m+2}\end{bmatrix}$$ and

$$\begin{bmatrix}w_1 & w_2 \\
w_3 & w_4\\
\end{bmatrix} \begin{bmatrix} k_{21} \\ k_{22} \end{bmatrix}
= \begin{bmatrix}c_{m+1} \\ c_{m+3}\end{bmatrix}$$

which allows us to compute the candidate key entries as $$
\begin{bmatrix}k_{11}\\k_{12}\end{bmatrix} = {\begin{bmatrix}w_1 & w_2 \\
w_3 & w_4\\\end{bmatrix}}^{-1} \begin{bmatrix}c_m \\ c_{m+2}\end{bmatrix}$$

etc. where we only have to compute the inverse of the plaintext matrix once in advance.

Then test these candidates on another part of the ciphertext (after WITH say) and check for sensible text. If we find it we have the correct $m$. The above holds if the crib WITH starts at a position where it is encrypted as (W,I) (T,H)
which you should try first so $m$ even.). If it is at another position, we get more equations (6 for 3 pairs of cipher text) in 2 more unknowns (the 2 two missing plaintext characters before and after the crib) and have to solve those (easy by computer).


RSA: What happens to restrictions of plaintext n, dependent on p and q? Ok - i will try to ask my question as clear as possible. Im getting a little deeper into the RSA-cryptosystem. At one point i'm a little confused.
We have a plaintext $x$ and ciphertext $y$, with

$x \in\Bbb Z_n = \{0,...,n-1\} $.

Additonally we choose $p$ and $q$ as primes. My source says $x$ must be less than $n$, which really makes sense to me. It proves that the RSA scheme works by using Euler's Theorem for:

$$
\\
$$

First case:
$gcd(x,n)=1$

$d_{k_{pr}}(y) \equiv  (  x^{\Phi(n)}  )^t \cdot x  \equiv   1\cdot\ x \equiv  x\  mod\ n     $

$$
\\
$$

Second case: $gcd(x,n) = gcd(x,p\cdot q) \ne 1$

So we can assume $x$ to be: $\qquad x = r \cdot p\ $ or $\ x = s \cdot q \qquad$ ($r\lt q$ and $s \lt p$)
Without loss of generality: $\qquad \ \ x=r\cdot p$
Implict we have: $\qquad \qquad \quad \ \ \ gcd(x,q)=1$

Euler's Theorem holds in the following form:

$\qquad 1 \equiv 1^t \equiv (x^{\Phi(q)})^t\ mod\ q. $

Substitution:

$\qquad (x^{\Phi(n)} )^t \equiv (x^{(p-q)(q-1)})^t \equiv ((x^{\Phi(q)})^t)^{p-1} \equiv 1^{(p-1)} = 1\ mod\ q. $

Using the definition of the modulo operator, we can show that:

$
\\ \qquad (x^{\Phi(n)})^t \quad = 1 + u \cdot q
\\ \qquad  x \cdot (x^{\Phi(n)})^t = x + x \cdot u \cdot q
\\ \qquad  x \cdot (x^{\Phi(n)})^t = x + (r\cdot p) \cdot u \cdot q
\\ \qquad  x \cdot (x^{\Phi(n)})^t = x + r \cdot u \cdot n
\\ \qquad  x \cdot (x^{\Phi(n)})^t \equiv x\ mod\ n .
$
$$
\\
$$
This proof seems plausible to me. Now my questions:

If $x \in \Bbb Z_n = \{0, ..., n-1 \}$ for $n=p \cdot q$, what happens to $n$ when $p$ and $q$ are not prime. Does this restrict the choice of an input $x$. For example, has $x$ to be less than $min(q,p)$? In this lecture Prof. Dr. Spannagel tolds the students that $x$ should be choosen always less than $min(q,p)$, to ensure that $gcd(x,n)=1$.
In addition, what happens if $p = q$ for $p$ and $q$ are prime. Does this affect our proof in case two?

The questions are not about argueing about the security of RSA and well choosen parameters $p$ and $q$. It's more about the restrictions on $n$ we will cause by choosing these factors.

Thanks in advance.

RSA has quite a few aspects, which are utilized implicitly, and these questions aim at those:

Concerning your first point about what happens if $x$ is not coprime to $n$, it does not compromise the correctness of the encryption and decryption, but if you find such an $x$, you also found a nontrivial factor of $n$. However, if $p$ and $q$ are prime, the probability to find such an $x$ is negligible (in the mathematical sense).
Concerning your first question, about what happens if $p$ and $q$ are not prime, is that you effectively weaken the scheme. For every known factor $f$ of $n$ you can reduce the RSA-problem into solving it in $f$ and $n/f$ and afterwards use the chinese remainder theorem to put them back together. An other minor aspect is, that finding $e$ might be more difficult (it has to be coprime to $\phi(n)$, otherwise decryption does not work any more, because it's not a bijection).
For your second question: If $p=q$, then $\phi(n)=\phi(p^2)=p(p-1)$ is not secret any more. Everyone can just compute $d$ by solving $ed=1$ mod $\phi(n)$. Effectively there is no trapdoor left anymore, which is required for a public key scheme to work.


Capital passphrases with rainbow tables? I'm currently trying to learn how rainbow tables work for a personal project of mine, but I am a little bit confused on how passphrases can be found. Here are the steps that seem do this, from the sources I have looked up online:

Take words, in this case passphrases, and hash them using a hash function
Reduce the hash, possibly to the first 5 characters
Repeat that possibly 100,000 times.
Keep the original "passphrase" and the last hash and store it
Repeat that for a certain amount of words/passphrases
For a given hash with an unknown plaintext passphrase, check if any of the hashes stored matches, if it does, start from the stored plaintext passphrase and keep hashing until you reach the passphrase hash (the one given without a plain text passphrase) and you're done. If the given hash (the one given without a plain text passphrase) does not match with any of the stored hashes, reduce the hash to 5 characters, rehash and try again.

If I got anything wrong or mixed up, clarification would be EXTREMELY appreciated. My question is how can rainbow tables find plain text passphrases, such as Password123, with a capital letter along with lowercase letters; since from my understanding hashes would look something like cb27b615a8a4e29fdf3e7c52cb09e5ef, with either all uppercase or lowercase letters? Thanks!

You should first understand that hashing (and modern cryptography in general) usually works with bits and bytes, and not directly with 'characters' such as 'abc'.

Before performing a cryptographic operation such as hashing or encryption, the input (in this case, the passphrase) is converted from it's encoded format (usually unicode or ascii) to bytes.

You can experiment at this website to gain an understanding of how this works. Note that the text 'abc' maps to bytes [61, 62, 63], but 'Abc' maps to [41, 62, 63].

Try calculating the SHA-256 hash of the strings 'abc' and 'Abc' at this website. You'll notice that they're completely different.

Finally, note that the output of most cryptographic functions is also returned in raw bytes, which can then be encoded to hex (such as your example above), base64, or any other number of encodings.

Encodings are completely reversible and don't use any keys, they're just a way of representing/storing binary information. Base64 is more efficient than hex encoding, and accordingly it is case-sensitive. Hex, on the other hand, is case insensitive, so 'cb27b6' and 'CB27B6' still map to the same bytes.

To answer your question, for a rainbow table to be effective, you would need to store the hash of all possible lowercase/uppercase combinations of the passphrase. It's also common to store variations of spelling, like substituting 's' for '$', and 't' for '+'.

Regarding the truncation - rainbow tables are limited by storage. To store the full hash of the many permutations of billions of inputs is expensive. Truncating the hash (ie, chopping off everything but the first 3 or 4 bytes) saves a lot of space, and if a match is found there's a strong likelihood that the full hashes will match, and it's very fast to verify.

Note that using a slow hash and salt will render rainbow tables ineffective.


How did the cryptographers of Bletchley Park figure out the chi stream of the Lorenz cipher? How did the Bletchley Park code breakers figure out the chi stream of the Lorenz cipher, that was obscured in the ciphertext, which British code breakers eventually decoded? It's written in The Rutherford Journal that John Tiltman deduced the key using a depth found on 30 August 1941. Since he couldn't figure how the key was generated, it was given to W.T. Tutte, who figured out how the key was generated without ever looking at the Lorenz cipher machine.
Jack Copeland writes in Colossus: The Secrets of Bletchley Park's Codebreaking Computers (p.364)

Here was a method of wheel setting! Δ(χ1+χ2) was a periodic sequence, supposed known, with a period of 41×31=1271. Lay it against Δ(C1+C2) in each of the 1271 possible relative positions and count the number of agreements for each one.

It's obvious that the British code breakers had the ciphertexts in hand, from which they could obtain the delta-ed version of the sum of the first and second impulse of an intercepted ciphertext, i.e., Δ(C1+C2). I would like to know how the code breakers figured out the delta-ed version of the chi stream of the Lorenz cipher machine, i.e., Δ(χ1+χ2).

The answer can be found here:

The initial function of Colossus was to help determine the starting
point of the wheels. Colossus read the cipher’s stream of characters
and counted the frequency of each character. Cryptographers then
compared the results to the frequency of letter distribution in the
German language and to a sample chi-wheel combination, continually
refining the chi-wheel settings until they found the optimal one.

The setting that gave the highest count of •s was found to be optimal (F. Carter, Codebreaking with the Colossus Computer, 2008, pp. 16-17).
They understood the settings of the wheels because of the extraordinary work of William Thomas Tutte, OC FRS FRSC. From Wikipedia:

At Bletchley Park, mark impulses were signified by x and space
impulses by •. For example, the letter "H" would be coded as
••x•x. Tutte's derivation of the chi and psi components was made
possible by the fact that dots were more likely than not to be
followed by dots, and crosses more likely than not to be followed by
crosses. This was a product of a weakness in the German key setting,
which they later eliminated. Once Tutte had made this breakthrough,
the rest of the Research Section joined in to study the other
impulses, and it was established that the five chi wheels all advanced
with each new character and that the five psi wheels all moved
together under the control of two mu or "motor" wheels. Over the
following two months, Tutte and other members of the Research Section
worked out the complete logical structure of the machine, with its set
of wheels bearing cams that could either be in a position (raised)
that added x to the stream of key characters, or in the alternative
position that added in •.


If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy? If one were to create a SHA256 hash using 256 coin flips converted to hex (which, as I understand it, is as "entro-phized" as one can capture in SHA256) then take that hash as a string, combine that with a hash of the word "cat" and hash the resulting 512 character string, would the resulting hash from that exercise be any less random than our "perfect" hash we began with?

My thinking is the final string would capture the same amount as the original randomness as what we started with because the "extra" entropy can not be captured and is lost. Is this the case and am I thinking about this correctly? Would hashing something with high entropy with something simpler ever cause a lower amount of randomness or does it only go up?

Thanks to anyone who can help explain this a little better.

A deterministic function $f(X)$ of a random variable $X$ never has greater entropy than the original random variable $X$.

(Side note: If you're not familiar with the technical terms random variable and expectation, or the definition of entropy in terms of them, I recommend you read up on some elementary probability theory first—the rest of this post will not make sense without these keywords!  In the sequel, ‘entropy’ can be taken to mean Shannon entropy or min-entropy—both work, and coincide on uniform distributions, but cryptography works primarily in min-entropy.  See this answer for a brief discussion of what entropy means from a crypto perspective.)

At best, if $X$ is a random $k$-bit string with uniform distribution and thus $k$ bits of entropy, the maximum possible, and if $f\colon \{0,1\}^k \to \{0,1\}^k$ is a permutation (a.k.a. bijection), then $f(X)$ also has $k$ bits of entropy.  If $f$ is not a permutation, then $f(X)$ has strictly less than $k$ bits of entropy—although perhaps not much less.

In this case, $f$ is SHA-256, which we might model by a uniform random choice of map $F\colon \{0,1\}^k \to \{0,1\}^k$.  There are almost certainly fewer than $2^k$ distinct outputs, because very few such possible values of $F$ are permutations.  Specifically, fix an output $y \in \{0,1\}^k$; for each input $x \in \{0,1\}^k$, we have $\Pr[F(x) = y] = 1/2^k$, and $F(x)$ is an independent random variable for every $x$, so
\begin{align*}
  \Pr&[\exists x. F(x) = y]
     = 1 - \Pr[\forall x. F(x) \ne y] \\
    &= 1 - \Pr[F(0) \ne y]\,\Pr[F(1) \ne y]\cdots\Pr[F(2^k - 1) \ne y] \\
    &= 1 - (1 - 1/2^k)^{2^k}.
\end{align*}
which, by linearity of expectations, is also the expected fraction of distinct outputs.  As $k \to \infty$, this converges to $1 - e^{-1} \approx 0.632$.

Thus, over a uniform random choice of $F$, the expected entropy of $F(X)$, or $\mathbb E_F\bigl[H[F(X)]\bigr]$, is about one bit less than the entropy of $X$, or $H[X]$, where $H$ is the entropy operator.

What about iterating SHA-256?  Do we lose a bit of entropy every time, so that $\operatorname{SHA-256}^{256}$ has zero entropy?  No.  If we independently chose another function $G\colon \{0,1\}^k \to \{0,1\}^k$, then over a uniform random choice of $F$ and $G$, the expected entropy of $F(G(X))$ might be about two bits less than the entropy of $X$.  But that's a bad model for iterating SHA-256, because we are restricted to the case $F = G$, in which case $F$ and $G$ are as far from independent as possible.

Rather, there's a good chance that for any fixed function $F$, there are many cycles on which $F$ is a permutation, and restricted to which $F$ thus preserves entropy.  There's usually one main big cycle, which lends itself to a drawing of a giant hairy rho: $\rho$.  In the limit as $\ell \to \infty$, $F^\ell(X)$ maps $X$ to an independent uniform random point on one of the cycles, the choice of cycle being weighted by the number of points on and leading to that cycle.

But in practical terms for cryptography engineering?  Usually we treat $\operatorname{SHA-256}(X)$ as a uniform random variable independent of everything else in the system (except where length extension attacks might be relevant) with entropy equal to that of $X$, or 256, whichever is smaller.


What is the purpose of Homomorphic encryption? Homomorphic cryptography is a kind of cryptography that allows you to do special math operations on the ciphertext, and the maths performed are identical to the obvious ones. For example, one person can combine two cached numbers, and decode the result, the sum will be two numbers.

What is the purpose of Homomorphic encryption?

In addition to the other answers: A secure secret-key homomorphic encryption scheme can be used to create a public-key encryption scheme.

If we consider encryption to be control of read and write abilities on data, then it's easy to see how this is the case.

With normal secret-key encryption:

only the key holder(s) can create ciphertexts (write permissions)*
only the key holder(s) can decrypt ciphertexts (read permissions)

With normal public-key encryption:

anyone with the public key (which is anyone, as it is public) can create ciphertexts
only the private key holder can decrypt ciphertexts.

With homomorphic secret-key encryption:

the key holder can create ciphertexts
anyone can manipulate ciphertexts (another form of write permission)
only the key holder can decrypt ciphertexts

This overlaps with the above definition for public-key encryption. While someone without the secret key cannot create a ciphertext for a given plaintext directly, they can do so if they are given pre-existing ciphertexts with known plaintext by the key holder.

An example

Assume the existence of a secure, secret-key, partially homomorphic encryption algorithm that supports integer addition on ciphertexts.

For the sake of simplicity, we will also assume that noise levels and resultant corruption of plaintext are not an issue (this is a real issue that many homomorphic encryption schemes suffer from).

A private key is simply a secret key $d$ for the secret-key encryption algorithm.

The nature of which is unspecified in this example, it would depend on the concrete scheme being used whether $d$ is a scalar, vector, etc.

A public key $\mathbf{e}$ of is a vector of encryptions of $1$ of length $n$ created using the private key with the symmetric encryption algorithm.

The public key operation generates a vector $\mathbf{r}$ such that $$m = \sum_{i=0}^{n}r_i$$ (secret splitting of $m$ into $n$ shares) and computes $$c \leftarrow \mathbf{er}$$

The inner product of $\mathbf{e}$ and $\mathbf{r}$.

The private key operation applies the decryption procedure from the secret-key cryptosystem to $c$ to recover $$1 * r_0 + 1 * r_1 + 1 * r_2 + \dots + 1 * r_n$$

Which is of course simply equal to $$m = r_0 + r_1 + r_2 + \dots + r_n$$

There are other possible public-key operations, e.g. based on subset-sum problems and/or LWE.

* Only the user with the secret key can create meaningful ciphertexts; An arbitrary block of bits of correct size is a valid ciphertext, but picking such a block of bits arbitrarily is unlikely to yield a meaningful plaintext with overwhelming probability


Triple-DES DUKPT CBC PIN variant vs Data variant Does any know the difference between triple des dukpt decryption algorithm with PIN variant and Data variant?

I have done Triple DES DUKPT PIN variant, which generate session key from KSN and BDK. And then decrypt message using the session key.

How about Data variant? How is it different from PIn variant?

BDK and KSN are used to derive a transaction key which is unique for that session. The are unique because KSN is updated after each transaction. Once this key is derived you apply different variants to get PIN, Data or MAC key.

For the PIN and MAC key: these variants are simply XORed with derived key. One more encryption is performed to calculate the data encryption key after applying variant.

These variants are fixed; you can refer to X9.24 Retail Financial Services Symmetric Key Management for more information.


I have created values for RSA encryption but it doesn't always work I am using the values as follows:

$(p, q, n, \phi(n), e, d) = (1033, 5039, 5205287, 5199216, 65537, 3784241)$

Yes, I have made sure $e$ and $\phi(n)$ are coprime.

For example, if I were to encrypt the value $13130$, I would get $4664915$ and then I decrypted $4664915$ and got $13130$.

The problem is when then I encrypted the number $1310731326$ and got $3386045$, when I went to decrypt $3386045$, I got $18660$ which is nowhere near $1310731326$.

I've been trying all day and still can't find the solution. Can someone help me please!?!?!

Your message has to be smaller than n to be correctly encrypted / decrypted with RSA.


Why would we want parallelizable authentication? I believe that parallelizable authentication schemes are superior from an aesthetic perspective and because most non-recursive calculations (e.g., CTR, ECB, PMAC, etc.) are better than recursive ones (e.g., CBC, OFB, CFB, CBC-MAC, etc.).

Most of the CAESAR candidates, i.e. GCM, OCB mode, PMAC, XOR-MACs, and protected counter sum provide parallelizable authentication while HMAC is not parallelizable.

One paper out there says that many schemes used by the CAESAR candidates, GCM, and XOR-MACs can be trivially broken by an incredibly unrealistic quantum attack (it turns the complexity from $O(2^{n})$ to $O(n)$ but requires a quantum entangled state that can only be generated with the key). Additionally, with or without quantum computers, many of these parallelizable authentication schemes only provide security up the birthday bound.  This makes it seem like a lot of the known parallelizable modes of authentication are not as strong as an HMAC construction.

Am I mistaken? Is there anything about most particular parallelizable methods that have drawbacks/weaknesses relative to HMACs? If so, what are they? And why do we seek parallelizable methods if that is the case?

If you have a vector unit on your CPU that can be used only by a single thread at a time but remains powered whether you're using it or not, it takes less time, and is therefore cheaper, to compute a parallelizable function using the entire vector unit than to compute nonparallelizable function using only a part of the vector unit.

If you have only three cycles per byte to spare in your computing budget, there is no way you will fit HMAC-SHA256 in that.  But you can easily fit Poly1305.  The more parallelizable the function, the more flexibility you have to adapt it to vector units of different sizes to maximize throughput subject to your power constraints.

The alleged quantum threat to these constructions posits the asinine model where the legitimate user reveals quantum superpositions of secret function evaluations to the adversary.  If you do your cryptography on a classical computer on ordinary bits, then the model is irrelevant.  If, under the currently unrealistic premise that quantum computers were actually capable of it, you did your cryptography on a quantum computer and enabled this attack model, you would be an idiot.  This model gives amusing theoretical results, but it is totally irrelevant to the real world.


Proof of work - 51% attack In the 51% attack on the Proof Of Work Consensus Mechanism, it's often said that you need more hashing power than the rest of the network combined. Though I can't understand why you need that much.

If we break the blockchain network down in Alice, Bob, Charlie and Eve, and they all currently are honest. They all have 1/4 of the total hashing power. From what I understand, they all compete against eachother to calculate the right hash of a block, and the one winning the race gets its block on the blockchain. This happens one time each 10 minutes. Since they're all competing, the hash-power used to create a block in 10 minutes, is 1/4 of the total hashing power.

Now eve decides to go rogue, and builds her own blockchain. The difference is now, that she don't compete with anyone. That means that she can generate a block every 10 minutes (ish) on her private blockchain, keeping up to speed with the rest of the network. Having just a bit more power, she can then build blocks faster than Alice, Bob and Charlie combined, since they are "competing". At some point Eve's blockchain grows larger than the others, and she broadcasts it, and Alice, Bob and Charlie will per the rules switch to Eve's blockchain.

In this scenario the network was compromised by only using 25%(+1) of the hashing power. So why would Eve need 51%? Doesn't she just need to be faster than the fastest honest miner?

Hope you can tell me why I'm wrong.

Since they're all competing, the hash-power used to create a block in 10 minutes, is 1/4 of the total hashing power.

That's not correct.

If the work effort is set to $n$, that is, it takes an expected $2^n$ hashes before someone finds a valid preimage.  If Alice, Bob, Charlie and Eve are all working equally hard, then we would expect that each one would end up computing an average of $2^n / 4$ hashes before someone finds a preimage.  It might be Alice, who has computed only $2^n / 4$ hashes, but still a total of $2^n$ hashes were computed.

So, if Eve goes off on her own, she'll need to compute her own $2^n$ hashes herself before she finds a preimage; in that time, Alice, Bob and Charlie will end up computing $3 \cdot 2^n$ hashes, enough to find an expected 3 links in the hash chain, before Eve can compute one - Eve cannot win this race in the long term.

(Note: this analysis rather assumes that when Alice finds the preimage, she instantly announces it, and the others immediately start searching based for the next preimage.  This isn't precisely true; however that isn't nearly a large enough effect to give Eve an advantage when she has only 1/4 of the computing power)


How are the PC-1 & PC-2 calculated for the DES block cipher? How  are the permuted choice tables - PC-1 and PC-2 - calculated for the DES block cipher algorithm?

These are not calculated, but as with the particulars of S-boxes, suggested and reviewed as part of the design.

These fixed values/configurations are intended to add certain qualities to the particular step of each round, essentially obscuring the final output as much as possible, in a non predictable way. As you can read on Wikipedia, there is some controversy involved in the development of the S-boxes.

  There was some criticism from various parties, including from
  public-key cryptography pioneers Martin Hellman and Whitfield
  Diffie,[1] citing a shortened key length and the mysterious "S-boxes"
  as evidence of improper interference from the NSA.


Laplace mechanism in Differential Privacy From The Algorithmic Foundations of Diﬀerential Privacy
It wrote that :

But from this pdf

I am confused which one is right, or I misunderstand.

In second method, after I compute Pr[v], and then what to do?

I am not sure how to implement the Laplace mechanism.

These two formulas are the same thing. The second formula is the probability density function of the Laplace distribution centered on 0 ($\mu=0$) — although rather than $Pr[v]$, the second PDF should probably have used a notation like $f(v)$ to make it clear that this is a probability density function and not the probability of returning exactly $v$.
If the question about "how to implement the Laplace mechanism" was referring to something you want to do in practice, then you probably don't want to do it yourself; but you want to use an implementation safe against floating-point attacks. Here's an example of open-source software you can use (disclaimer: I'm part of the team behind that library).


Is CBC mode encryption vulnerable to a reordering attack? I know that, if CBC-MAC is used in such a way that the tag is the concatenation of all the blocks' outputs (and not just the last one), it's insecure under CPA for the simplest case of 2 blocks CBC-MAC where:

the message is $m=m_1\mathbin\|m_2$, where $|m_1|=|m_2|$ equals the block size of the cipher, and
the tag is $t=t_1\mathbin\|t_2$, where $t_1 = F_k(m_1)$ and $t_2=F_k(t_1\oplus m_2)$.

In this case, the attacker can change the plaintext and create a valid tag of reverse order. The new message will be $m'=m'_1\mathbin\|m'_2$, where

$m'_1=m_2\oplus t_1$,
$m'_2=m_1\oplus t_2$, and
$t'=t_2\mathbin\|t_1$.

Is a similar attack also possible for the CBC encryption mode (where we have a random $IV$ xored to $m_1$)?

EDIT: My question actually is whether a CPA attacker (who knows $c=IV\mathbin\|c_1\mathbin\|c_2$ and $m=m_1\mathbin\|m_2$) can modify the ciphertext that is sent to the destination and be able to predict what the plaintext resulting from it will be?

Yes.  Assume that the attacker knows the ciphertext $c = c_1 \mathbin\| c_2$, the initialization vector $v$ and the plaintext $m = m_1 \mathbin\| m_2$.  This tells them that

$D_k(c_1) = m_1 \oplus v$ and
$D_k(c_2) = m_2 \oplus c_1$,

where $D_k(\cdot)$ denotes block cipher decryption under the (unknown) key $k$.

In particular, this implies that, if the attacker reverses the order of the ciphertext blocks to produce the modified ciphertext $c' = c_2 \mathbin\| c_1$, then they will know that it will decrypt to $m' = m'_1 \mathbin\| m'_2$, where

$m'_1 = D_k(c_2) \oplus v = m_2 \oplus c_1 \oplus v$ and
$m'_2 = D_k(c_1) \oplus c_2 = m_1 \oplus c_2 \oplus v$.

There should be nothing particularly surprising about this: like all non-authenticated block cipher modes of operation, CBC mode is known to be malleable, meaning that an attacker who can change the ciphertext is also able, at least to some extent, to predict the effects of the changes on the resulting plaintext.  If you don't want that (and you usually don't), you need to use an authenticated encryption mode, possibly constructed by combining a conventional mode like CBC with a secure MAC.

(In fact, a further attack on CBC is possible if, as usual, the initialization vector $v$ is transmitted alongside the ciphertext: in that case, the attacker can change the first block of the plaintext to anything they want, without affecting the other blocks, simply by changing the IV.)


How to make PKCS conformation oracle for trying Bleichenbacher’s RSA attack? I was trying to understand Bleichenbacher’s CCA attack and thought of work it out in python. Can some one throw some light on the the logic behind the oracle used to check PKCS conformation? Will a cipher's parity check yield anything useful?

I unfortunately don't have enough reputation to comment, forgive the answer that is a link to another answer. Your question is explained well in this answer:

https://crypto.stackexchange.com/a/12706/17884


Explanation of the Decision Diffie Hellman (DDH) problem. I'm extremely new to crypto, and very much inexperienced. Lately I've been reading about the Diffie-Hellman key-exchange methods, and specifically about the computational diffie-hellman assumption vs. decision diffie-hellman assumption. Specifically I'm referencing Dan Boneh's paper on DDH problem. However, I'm having some trouble understanding the difference between CDH and DDH. What are the differences? Similarities?

The Computational Diffie-Hellman (CDH) problem is:

  Given some group $G$ and group element $g$, and the elements $g^a$ and $g^b$, compute the value $g^{ab}$.

The Decisional Diffie-Hellman (DDH) problem is:

  Given some group $G$ and group elements $g$, and the elements $g^a$, $g^b$ and $g^c$, determine whether $g^c = g^{ab}$

These are obviously related problems, the difference is that the CDH problem asks us to derive the DH shared secret, while the DDH problem just asks us to recognize it.

In addition, the CDH problem appears to be potentially harder, in this sense: if we're given an oracle to solve the CDH problem, we can easily solve the DDH problem (simply by handing $g$, $g^a$ and $g^b$ to the oracle, have it compute the value $g^{ab}$ and comparing that value to $g^c$.  In contrast, there's no known generic way to solve the CDH problem given a DDH oracle.

As for why the DDH problem comes up so often (and in cases where one would naively expect the CDH problem to to appropriate), well, many protocols do a DH-type computation, and then use the value $F(g^{ab})$ (for some function $F$); breaking the protocol may allow an attacker to recover the value $F(g^{ab})$.  Now, recovering this value would allow us to solve the DDH problem (by comparing that value to $F(g^c)$); hence, breaking the protocol would allow us to solve the DDH problem; or equivalently, if the DDH problem is hard, the protocol is secure.  However, if the function $F$ is one-way, recovering the value $F(g^{ab})$ doesn't give us the value $g^{ab}$, and so there is no reduction of the security of the protocol to the CDH problem.


Is it possible to use crib drag on base64 cipher text? I am pretty new to the cryptography scene but I wanted to know if it is possible to use crib dragging on cipher text which doesn't contain words? This data would be encrypted using the same key with a one time pad and the data is encoded using base64 before it is encrypted.

For example,

key = [1, 2, 3, 4]
message1 = [C, B, D, K]
message2 = [H, K, L, U]
encryptedMessage1 = [D, D, G, O]
encryptedMessage2 = [I, M, O, Y]

(yes I know this isn't exactly base64)

So if we XOR these two encrypted messages together we may or may not get CBDK or HKLU based on the word used for cribbing and even if we do get one how can you verify that it is the correct message?

Again total noob and trying to teach myself. ;)

Yes, it is possible to use crib dragging. It is easy to prove this: you could just search for the base 64 encoded version of the crib. This would work even if you would simply use search for a recurrence of the crib every 4 characters because that's the amount of base 64 characters that are needed to encode 4 bytes. So the chance of success would be diminished, but it is still possible.

It is also possible to perform crib dragging over byte boundaries in base 64, but then you may need to check for multiple possibilities that could be valid. So the chance of success is much lower if you start in the middle of a base 64 character.

You can of course guess the characters before the crib itself as well, so the extended crib can still be moved across the boundaries. You'd need to guess up to 3 characters though.


Security of Pohlig-Hellman exponentation cipher? I am looking into implementing Pohlig-Hellman exponentiation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. Does anyone have some reference that might be helpful in determining the minimal prime number one should use in order to ensure the algorithm is safe enough for various applications?

You need a large random prime modulus where the discrete log is hard.  Read about how to choose a prime so the discrete log is hard.  Also, you want $p-1$ to have as few small factors as possible.  Therefore, the short version is, I suggest you choose a large random 2048-bit prime $p$ such that $(p-1)/2$ is prime.

However, Pohlig-Hellman has some serious issues.  It has very poor performance, compared to other symmetric-key ciphers.  Also, it has no randomization, so it is not semantically-secure (it is not IND-CPA secure) in its standard form.  I don't know of anyone who uses the Pohlig-Hellman cipher in practice, in its standard form; it is more of theoretical interest than practical interest.

What exactly do you want to do with the Pohlig-Hellman cipher?  What exactly is your application?  Why do you want to use the Pohlig-Hellman cipher?  There might be better solutions.


How to calculate time needed for decryption of 64-bit key I am having trouble figuring out how long it takes to decrypt a 64-bit key, given that a computer can do 1 billion trials per second. I know that there are $2^{64} = 1.844 \times 10^{19}$ possible keys for this key size, but then how do I go about figuring out the rest? If there is a formula for this, I would be very curious to know what it is.

If you measure the number of keys you can guess per second (as suggested in the comments) you can calculate from there. As a frame of reference, if you can calculate 1,000,000,000,000 (1 trillion) keys per second, the time to break a 64-bit key would we an average of 15.25 weeks (106.75 days), with the longest possible time to break being 30.5 weeks (213.5 days).
You need to benchmark the number of keys per second on your own system to know the time it would take for you. If you can calculate half the keys, it takes twice as long. If your system calculates 10 trillion keys/sec it would take only $\frac1{10}$ the time (10.675 days average, 21.35 days max). I think you get the picture.


Why is encrypting a key under itself dangerous? I'm currently self-studying to try and understand more about cryptography for work. I'm on question 2.16 on A Graduate Course in Applied Cryptography
.

For part a), we're given a cipher $E$ that's semantically secure and asked to create $\hat{E}$ where $\hat{E}$ becomes insecure when the adversary is given $\hat{E}(k, k)$. Since I can't control the details of $E$, I figure $\hat{E}(k, k)$ must somehow reveal the key or some key generation algorithm to the adversary, since anything else should be public already (and yet still semantically secure).

At the same time, any $k$ seems like it should be a valid message, so we have to explicitly know the answer to $\hat{E}(k, k)$ (and can't just stumble upon it when trying $\hat{E}(k, m)$).

To me, this seems to contradict and thus I'm stuck. What am I missing?

Update:
I've thought this a little more through and may have some further ideas.

The definition I'm using to verify "semantic security" is that where an adversary submits $m_1, m_2$ and receives $c_x$. At this point, they should have no advantage in guessing which message was encrypted. However, when given $E'(k,k)$, they gain an advantage.
To me, this says that $E'(k,k)$ must somehow reveal information about k, since the scheme should be public by default (Kirchoff's Principle).
Suppose $E'(k, m) = E(k \oplus m, m)$
Therefore, $E'(k,k) = E(0, k)$. Since the decryption alg D should be public, I can decrypt $D(0, E(0, k)) = k$, and thus by giving the adversary $E'(k, k)$ I have given the key.
The adversary submits $m_1, m_2$. Upon receiving $c_1$, they know $k$, and trivially calculates which message was encrypted.
To adjust for the keyspace being smaller than the message space, allow for any excess bits in $k \oplus m$ to be truncated to $|k|$.

Thoughts? Does this work?

Let $E$ be your cipher.
Consider the following cipher:
$$E_{k}'(m) = \begin{cases}
k & m =k\\
E_k(m) & \text{else}
\end{cases}$$
I believe you should be able to reduce the security of $E'$ to the security of $E$ in a rather straightforward manner.

This is a fairly important notion in general though.
The notion of "being secure, even if one gets encryptions of functions of the secret key" is known as Key Dependent Messaging security in general.
It's a property that (among other things) so far we seem to require to build FHE, but cannot prove that particular FHE schemes have it (instead we generally make the "Circular Security assumption").

Matthew Green has a blog post on it if you want a slightly higher level viewpoint on the topic.


Reference for the Security Analysis of Ring-LWE Can someone please share a link of any research paper or web-page analyzing the security of Ring-LWE? Essentially, how should I choose my parameters to get security equivalent to 128-bit or 256-bit?

You should visit the Homomorphic Encryption Standardization web page. There you can find Homomorphic Encryption Standardization.

Also, there is a workshop The Second Homomorphic Encryption Standardization Workshop there you can find this document

Homomorphic Encryption Standard see section 2.0.3

I hope, all this will help in your research.


Is it impossible to have a decentralized service using email addresses as login? Let's say we have a decentralized service S distributed on a network of 1000 nodes/servers. Is it possible to have a registration/sign up scheme using email address as login?

I see two problems:

(Ignored for this question) Probable low deliverability rate for emails sent from nodes of a decentralized network to major email providers (Gmail, Yahoo, etc.); this is not a cryptographic problem, let's ignore this problem here.
Another real problem described in the following example workflow:

UserA, owner of userA@example.com, signs up to the service S (e.g. with a registration form on one of the website mirrors provided by the network)
A signup token f9x372d2aff0 is stored in PendingRegistrations database of the network by one of the node, and a confirmation email is sent by one of the nodes to userA@example.com
UserA opens his mailbox and sees a new email "Please confirm you want to signup to service S by clicking on http://203.0.113.2/register/userA@example.com/f9x372d2aff0"
UserA clicks on the link, the token is compared to the one in the PendingRegistrations database of the network, if it matches, he can finish the registration process since he has proved he's the legit owner of userA@example.com

Now:

Malicious UserB (who doesn't run a node himself) cannot create an account named userA@example.com, because he will have no access to the token that will be sent to userA@example.com's mailbox
Malicious UserC, who runs a node himself, CAN create an account named userA@example.com: he can go on the website, fill the registration form, and then observe the PendingRegistrations database and get the token and register the account himself. Or alternatively: he could observe the outgoing emails of the server, and see the link which will be sent to userA@example.com, and get the confirmation link.

This is close to Zooko's triangle principle, but I don't see how the famous solutions for it (e.g. Swartz's solution) can solve the problem here.

Is it impossible to have a decentralized service using email addresses as login, or can asymmetric encryption (public key / private key) help here?

Note: Any email going out from a node, sent to a user, has to be "cooked" by a node of the network. So I would say: "Any string that will be viewed by an email recipient who will open the email received in his mailbox, can also be viewed by the node owner/email-sending-server owner", thus making the problem difficult. It seems obvious, but maybe is there a clever solution?

The core of your question is "Is there an attribute that an 'owner' of userA@example.com can be proven to have, and which no on else can be proven to have?" This heavily depends on the security of the email system, which, in general, is quite poor. Another central question is what "registration" even means. Presumably, it means "proving" one's identity, but proving it to whom, and how do others know that it has been proven? There has to be some process by which the "network" verifies identity, and then there has to be some process by which users verifies that the network has verified identity. Fully answering your question requires a precise formulation of what those processes are.

Ultimately, the only two possible unique attributes that an "owner" could have is the ability to send email, and the ability to receive/read email. Any other attributes, such as the ability to sign with a private key (asymmetric encryption) would mean that you're not basing it solely on email anymore. At that point, it's like asking "Is it possible to open a bottle with a spoon, if you also have a bottle opener?"

If you are confident on being able to detect email spoofing, then you can just have someone choose a private and public key, send their public key from their email to the nodes, and then sign everything with their private key.

If you're not confident that you can detect email spoofing, but you are confident that it is possible to send a message in such a way that only the "owner" of an email address can read it, then it's impossible for any single message to generate any attribute unique to the new user; any information sent in the email, the sending node also has. So you will have to have "the network" in general send multiple messages from multiple nodes, each with their own token.


Generating and distributing a secret without trusting the source I have multiple entities (servers) that all share a private secret already.
Those servers need a rotating secret (TTL a few hours). All servers must have the same set of secrets at all times.
I have another server (command & control) with a communication channel to all my clients.
I want the command & control to handle the generating and rotating of the temporary secrets.
I also don't want the command & control to ever know the temporary secret.
So basically:

command & control generates a random blob
command & control distributes the blob to clients
clients use their shared secret to reduce the blob into a common secret (using I presume a pseudo-random cryptographic function)
the final secret needs to be ~80 bytes

What would be the best practices to do this?

You'd use a KBKDF on the clients, using the earlier secret as Input Keying Material (IKM) using the random as salt or Info input. KDF's generally have an output size parameter as well.
Currently HKDF is considered a good KDF, and if you use the full function it supports a salt.
Basically you would be implementing a so-called ratchet, where each key depends on the previous one, but doesn't provide any information about the previous keying material.


Finding discrete logarithm with baby-step-giant-step algorithm I am trying to use the Baby Step Giant Step algorithm to find discrete logarithm in:
$$a^x= B  \pmod p$$
with using BSGS:
$$x = im+j$$
$$a^j = B a^{-im}$$ where
$m = \sqrt{p}$

Wikipedia says:

  A cyclic group of order $p$, having a generator $\alpha$ and an element $B$.

But $p$ is a 158 bit number. Hence $m$ is too large and I know that $j$ is not a very big number,  $j < k$, where $k \ll n$.
I try to limit test values for $j$ and $i$ by defining $n$ as the next prime of $k$, but in this case I have this problem:

$$x = im+j \pmod {\operatorname{nextPrime}(k)}$$

$$a^x = B\pmod p$$
and when I try $B a^{-im}$ it does not give me $a^j$  because $B$ is actually $a^x \pmod p$ and I cannot find it in the lookup table I have created using values of $a^j$.

How can I solve this?

To search for the values $a^x$ in the range $0 < x < k$, what you need to do is set $m = \sqrt{k}$ (rounded up), and then do the Baby Step/Giant Step algorithm for $0 \le i, j < m$.

That is, you generate the values $a^0, a^1, ..., a^{m-1}$ and the values $B\cdot a^{-0}, B\cdot a^{-m}, B\cdot a^{-2m}, ..., B\cdot a^{-(m-1)m}$; if $x<k$, then there will be a colliding pair $a^j = B\cdot a^{-im} = a^x \cdot a^{-im}$ with $x = j +im$


Has any crypto hash function been proven to be surjective? This answer claims that "it is not proven that all outputs of SHA-1 are possible." Has any crypto hash function been proven to produce all possible outputs (i.e., to be surjective over the codomain of all possible numbers $[0, 2^n]$, where $n$ is the number of bits of the hash)?

The answer is YES for constructions of hash functions that are not used in practice. For example, there is a construction by Damgård that is based on the discrete log problem and works by computing $h(x_1\|x_2)=g^{x_1}\cdot h^{x_2}$, where $g$ is a generator of the group. If $h$ is chosen randomly in the group, then it is hard to find a collision in this function, unless you can solve the discrete log problem. By applying the Merkle-Damgård transform, you get a hash function that takes inputs of any length. Thus, this is a collision resistant hash function.

It is easy to see that this function is surjective. Specifically, $g$ is a generator of the group, so for every $h'\in\mathbb{G}$ and for every $x_2$ there exists a value $x_1$ such that $g^{x_1}\cdot h^{x_2} = h'$.


What is the notion of an interactive assumption? In this paper: Sequential Aggregate Signatures with Short Public Keys: Design, Analysis and Implementation Studies the authors sell the paper as the first who propose Aggregate signatures without interactive assumptions as LRSW but with static ones. What renders an assumption interactive? The fact that is not a standard: DDH, CDH, DL, QR, RSA ,etc well known assumption?

You can define most hardness assumptions in terms of a game played with an adversary. See Shoup & Bellare-Rogaway for details.
Example: You can define DDH assumption in terms of the following game:

Challenger picks a random bit $\beta$; and random $a,b,c \gets \mathbb{Z}_p$. He computes $A = g^a; B=b^b$ and $C = \begin{cases}g^{ab} & \mbox{if }\beta =0 \\ g^c& \mbox{if } \beta=1\end{cases}$ and sends $A,B,C$ to the adversary.

Adversary tries to guess $\beta$.

Example: You can define CPA-secure (public-key) encryption in terms of the following game:

Challenger generates keypair $(sk,pk)$ and gives $pk$ to the adversary.

Adversary chooses two plaintexts $m_0, m_1$.

Challenger chooses random bit $\beta$ and gives $\textsf{Enc}(pk,m_\beta)$ to the adversary.

Adversary tries to guess $\beta$.

The first game is non-interactive, with the adversary simply receiving values (the final guess of the adversary is not really counted). So DDH is a non-interactive assumption.
The second game is interactive since the adversary is allowed to choose his plaintexts after seeing the public key. So CPA security is an interactive assumption.
Now suppose you're trying to prove that some interactive system of yours is secure. You can always just take "my system is secure" as an assumption, but you haven't actually done anything in this case. On the other hand, if you base the security of your interactive system on a non-interactive assumption, then you must have actually done something non-trivial. In general, we want to base security on the simplest possible assumptions, and interaction is a natural way to measure the "simplicity" of an assumption.

Victor Shoup. Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332, 2004.
Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In EUROCRYPT 2006, LNCS vol 4004, p409-426.


Problem on Elliptic Curve Point Doubling Given an elliptical curve e.g. from “Understanding Cryptography” by Parr & Pelzl §9.2 Example 9.5:

$y^2 = x^3 + 2x + 2~~~~ mod~17$

And given a primitive $P = (5, 1)$, the book indicates:

  We compute now all the "powers" of P.

They then provide a table:

$2P = (5, 1) + (5, 1) = (6, 3)$

$3P = 2P + P = (10, 6)$

$...$

$18P = (5, 16)$

Unfortunately it is not apparent to me what action they are performing with the addition ($+$), or what they mean by "powers".  What operation is being performed to go from $(5, 1) + (5, 1)$ to $(6, 3)$, and so on?

The obvious operation (i.e. what Wolfram alpha does) of $(5, 1) + (5, 1) = (5 + 5, 1 + 1)$ yields $(10, 2)$.  There are a plethora of other possible combinations of operations that one could try, but I'd just be guessing.

Generally, given the secret, ordinarily labeled $d$, how ought one calculate $dP = P + P~ +~ ... ~+~ P$?

(This presumably computes the public key $X$ & $Y$ points, from $d$ and the $Gx$ and $Gy$ parameters)

While it is a rather core operation, and likely quite basic, I have found no illustrative examples and at-best convoluted implementations.  I'll keep looking, but I thought that a good answer might be a useful for the next person searching.

Edit

This exact example also appears and is discussed at: https://math.stackexchange.com/questions/430836

The point addition $P+Q$ and doubling $2P = P +P $ in Elliptic Curves $E$ are not just x,y coordinates in the Euclidean Plane that you can add the coordinates. One can find the rules in Wikipedia;

Point addition: With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.
Point doubling: Where the points P and Q, are coincident (at the same coordinates), addition is similar, except that there is no well-defined straight line through P and Q, so the operation is closed using limiting case, the tangent to the curve, E, at P and Q.

Given the Elliptic curve $E:y^2= x^3+a x + b$ and a point $P=(x_p,y_p)$ on the curve, the doubling $R=2P = P + P$ can be calculated by:
\begin{align}
\lambda &= \frac{3 x_p^2 + a }{2 y_p}\\
x_r &= \lambda^2 -2 x_p\\
y_r &= \lambda(x_p-x_r) - y_p
\end{align}
The curve is defined in modular arithmetic $\pmod{17}$, therefore convert $1/2$ into $2^{-1} \equiv 9 \bmod 17$ and find the inverse by extended GCD algorithm.
$\lambda = (3\cdot 5^2 +2)\cdot 9) \equiv 13 \bmod 17$
$x_r = \lambda^2 - 2 x_p  = (13^2  -10 ) \equiv 6 \bmod 17 $
$x_y = \lambda(x_p - x_r)-y_p =  13 \cdot ( 1 - 6) - 1 \equiv 3 \bmod 17$
$$(5,1) + (5,1) = (6,3)$$


how does an initialization vector work? Can somebody please explain how an initialization vector works.

My current understanding is that it is used to prevent 2 of the same messages looking identical after encryption, but isn't this the same as what a salt does?

How is it different from a salt?

Indeed both have the aim to prevent same messages "encrypting" to the same plaintext.
The difference is the context.

People speak about using IVs if they want to use them in blockcipher modes, like CTR or CBC.

People use the word "salt" if they want to refer to something that is stored in public but must be somewhat random and large. Usually this applies mainly to password hashing schemes like scrypt or bcrypt.


Why does RSA need two prime numbers? I'm having a hard time understanding the purpose of having two primes $p,q$ for RSA to work. To illustrate my point, imagine only one prime ($p$) is used.

Alice, the encryptor, can take the public encryption exponent $e$, which Bob, the decryptor, created (along with the private exponent $d$) to satisfy
$$ed\equiv 1\pmod{p-1}$$
Alice then encrypts $M$, sending $C=M^e$ (the full value without a modulus) to Bob.

Bob receives $C$ and retrieves the message: $$C^d\pmod p$$
$$=M^{ed}\pmod p$$
$$=M^{(p-1)k+1}\pmod p$$
$$=M\pmod p$$
$$\text{(by Fermat's Little Theorem)}$$
Assuming an attacker cannot guess $p$ from $e$, this should be secure. Instead, RSA  creates exponents according to $$ed\equiv 1\pmod{(p-1)(q-1)}$$
and decrypts with
$$C^d\pmod p$$
$$=M^{(p-1)(q-1)k+1}\pmod p$$
$$=M\pmod p$$
$$=M\pmod q$$
$$=M\pmod {pq}$$
From this, it seems that the only benefit of using two primes is so that Alice can take a take a modulus before sending the ciphertext. If only one prime is used, Alice could send the ciphertext $\mod p$ and preserve correctness, but then she could use $p$ to derive  $d$, whereas in the two prime version, she can still take a $\mod n$ without knowing $p$ or $q$. I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice. Is this the only reason? And if so why is the concept of factoring a semi-prime number so central to the idea of RSA?

"I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice."

Yes, modular exponentiation is much faster.

How much do you think a number expands if you perform non-modular exponentiation?

And what's keeping an adversary from just trying all possible inputs, and encrypt them to see which one matches?

You can of course random pad $M$ with e.g. 128 random bits, but then your input will grow even larger, the exponentiation slower and the result even larger.

But most importantly, what's hard about calculating $\sqrt[e]C=\sqrt[e]{M^e}=M$ if $e$ is known? I don't think that that's a hard problem even if $e$ is very large. For a large $e$  the calculation really becomes problematic because the result size would be humongous anyway.

Of course, your encryption function needs to be irreversible without the private key value - in this case $d$ - and it isn't.


Is it safe to reuse the same nonce for decryption an indefinite amount of times in this context? I'm creating a password management application and I'm considering using the following procedure to keep passwords safe:

Asking the user for raw_password, for example "MyLongMasterKeyPassword"
Generating master_key from raw_password with Scrypt and a random salt
Storing the salt (kept public)
Asking for raw_message (the password to store)
Generating cipher using AEAD-ChaCha20Poly1305IETF and generating a random nonce, and then asking for AD(Additional authentication)
Storing the nonce
Encrypting raw_message with cipher, nonce, and AD, then using the nonce once for encryption, that returning cipher_text
Storing the cipher_text
Decrypting cipher_text with stored salt and nonce, then asking for AD and raw_password to regenerate the master_key with the stored salt, and then generating a cipher with the master_key and stored nonce, which returns the decrypted_message (a password, probably)

Now, the question is, is this procedure safe? Specifically, is it safe to re-use the same nonce for decryption an indefinite amount of times, if you only use it once for encryption?

Specifically, is it safe to re-use the same nonce for decryption an indefinite amount of times, if you only use it once for encryption?

Indeed, all good security definitions (under which ciphers are proven secure) will place no restrictions on the input of the decryption algorithm. The intution behind this is that the the input to the encryption algorithm will be send over the network at which point anything can happen to it.

Security only breaks down if you encryption two different messages using the same key-nonce pair.

  Now, the question is, is this procedure safe?

Yes. In fact the encryption scheme is essentially a reinvention and instantiation of PKCS#5's PBES2 which is provably secure1 (even if you were to use a fixed nonce). Your parameter choice in this case is to use randomized-nonce ChaCha-Poly for encryption and scrypt for key-derivation.

1: Our local pedants may note that the security definition of LORX from that paper only implies CPA-security, but an extension to CCA-security definitions should be straightforward as the proof essentially relies on hiding the key from the adversary and then "inheriting" the encryption scheme's security properties.


Check if two ed25519 points are equivalent How to check if two points are equivalent given their projective coordinates (XYTZ)?

For example if I do unproject() of a point to pass from XYTZ to XY coordinates and then I come back to XYTZ coordinates, the new XYTZ coordinates are different respect to the original ones.

How can I be sure that the two points are equivalent in C if they are represented in the following way:

struct ed25519_pt {
    uint8_t  x[32];
    uint8_t  y[32];
    uint8_t  t[32];
    uint8_t  z[32];
};

Short answer:

The affine coordinates are (X/Z, Y/Z).

So, check that Y1*(1/Z1) ≡ Y2*(1/Z2) and that the signs of X1*Z1 and X2*Z2 are the same.

Z being 0 represents the point at infinity.

Slightly longer answer:

Think about (X, Y, Z) as a fraction representation of (X', Y') with X' = X/Z and Y' = Y/Z. T is just X*Y and is not relevant here.

What you mean by "unproject" is going from a fraction to a scalar. Once this is done, you get something equivalent, but the denominator is lost.

You can go back to a fraction representation by setting the denominator to 1. This is what happens when you go from an affine representation to a projective or extended one.

(X, Y, Z) may look different after a round trip, but this is the same set of affine coordinates, just with a different denominator Z.


Elliptic curve over prime field with high order roots of unity Suppose I have an elliptic curve defined over a prime field $\operatorname{GF}(p)$ where $p$ is a large prime (e.g. 256-bit). Suppose also that $p = kn +1$, where $n$ is a relatively large power of $2$ (e.g. $2^{32}$). This structure implies that $\operatorname{GF}(p)$ has $n^{\mathit{th}}$ roots of unity.

My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?

My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?

Not particularly; the factorization of $p-1$ is not specifically relevant to the strength of a curve over $\operatorname{GF}(p)$.

Now, it is quite relevant to the strength of the group $\mathbb{Z}_p^*$; however that's because the order of the group is always $p-1$ (assuming $p$ is prime), and the factorization of the group order is quite relevant.  However, the elliptic curve (in general) doesn't have order $p-1$; instead, it is $p + \delta$ for some $|\delta| < 2\sqrt{p}$ (the exact value of $\delta$ depends on the precise curve you pick), and it is the factorization of $p + \delta$ which is important.


UC-framework: Simulating specific cases (proof in PVW) I am struggling to understand the proof of security in the UC-framework of the OT by PVW.

The cases I don't understand are the cases where:

i) Both parties are corrupted. In this case, they say that the simulator just lets the adversary generate and exchange all the messages. But isn't the simulator supposed to extract their inputs? What does the simulator sends to the ideal functionality in this case? How is this case indistinguishable from the ideal-world execution?

ii) Both parties are honest. In this case, they say that the simulator just simulates internally the protocol between the parties and delivers the exchanged messages to the adversary in the real-world. I don't quite understand how this simulation is indistinguishable from the ideal-world execution because the simulator does not have access to the inputs of the parties in the ideal world. So, it is unlikely that the parties in the simulated protocol end up with the same inputs and outputs. What am I missing in this case?

Thanks!

These two cases are trivial cases, usually don't need to argue about because they are definitely simulatable.

In the first case, both parties are controlled by the adversary. In the simulation, the simulator simulates both the corrupted sender and the corrupted receiver. The simulator can simply use the adversary as a subroutine to simulate each party, generates the messages to be relayed by environments. There is no need for the simulator to extract the adversary's input when all parties are corrupted by the adversary. The view will be indistinguishable from a real view because the adversary is the same in the simulation and in the real execution. Note that in this case simulation can be done but no security can be achieved, as the adversary has already corrupted all parties (nothing is left to be secured).

In the second case, both parties are honest, thus they will follow the protocol (which means they will use whatever input they have). The simulator is given their inputs  at the beginnning at the simulation and can just follow the protocol to generate the messages. The view will be identically distributed as in a real execution where the two parties are honest. This case is trivially secure because there is no adversary at all.


Problem with RSA deciphering I don't quite get the algorithm yet. Sometimes it works and other times it doesn't,so clearly I am overseeing or misunderstanding something.

I will just write what I did.
My $N=143$ and has factors $p=11$, and $q=13$.
To determine my second public number:
$R=(p-1)(q-1)= 10 \cdot12=120$. So the second number can not be a factor of $120$. I figured $e=7$ would be fine.

I simply want to message $'7'$. So $\mod\frac{7^7}{143}= 6$ will be my message.

My friend wants to decode it and needs to exponentiate this number by $d$.
$d=\frac{R+1}{e}=121/7$ But this should be natural number right?

I noticed it doesn't work for $e=9$ as well. Even though it is not a factor of $120$. It does work for $e=11$.

Should $e$ be chosen so that it is a factor of $R+1$?

For textbook RSA, we have

Key-Gen

The modulus $n$ must be a product of two distinct random large primes due to the security, $n = p \cdot q$

in your case $n=143 = 11\cdot 13$

For finding the primes, the probabilistic Miller–Rabin primality test, it should be enough. Note that the Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations, $k$; $$\Pr( p\text{ is not prime} ) \ll \frac{1}{4^k}$$ and can be stated as $$\log_2(\Pr( p\text{ is not prime} ))\ll-2k$$ This is a rough calculation, and as noted by fgrieu, the probability is approaching 0 as the size of the number to be tested increases. The FIPS 186-4 table C.3 provides specific numbers for $k$;

for 512 bits gives $k=7$ rounds with $\log_2(\Pr( p\text{ is not prime} ))<-100$,
for 1024 bits gives $k=4$ rounds with $\log_2(\Pr( p\text{ is not prime} ))<-100$, and
for 1536 bits gives $k=3$ rounds with $\log_2(\Pr( p\text{ is not prime} ))<-100$.

The factors of modulus are $p=11$ and $q =13$
$\varphi(n) = (p-1)(q-1)$, in your case  $\varphi(143) = 10\cdot 12 = 120$,

Actually, we prefer $\lambda(n) = \operatorname{lcm}(p,q)$ and this will give us the smallest private exponent. That can be helpful for signature calculation speed, and actually, one should use the CRT method ( see the last bullet of Key-Gen)

The relation is;
$$\varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1)$$ and this implies that $\lambda(n)| \varphi(n)$
The public exponent $e$ is chosen relatively prime to $\varphi(n)$, so $e=7$ is fine. Normally the $e$ is chosen advance in $\{3, 5, 17, 257, 65537\}$. If the $\gcd(e,\varphi(n)) \neq 1$ then a new modulus is generated.

$(n,e)$ makes the public key to distribute.
The private exponent $d$ is the inverse of $e$ modulo $\varphi(n)$, i.e. $d\cdot  e \equiv 1 \bmod \varphi(n)$, in your case $d=103$. This can be used with the Ext-GCD which result in a Bézout's identity $ e \cdot x + n \cdot k =1$. Take modulus $n$ then $x$ is the inverse of $e$.

$(n,e,d,p,q, d_p, d_q, q_{inv})$ is your private key. One can use CRT to speed up the decryption up to 4 times.

Encrypt

$c = m^e \bmod n$

The $m \in [0,n)$, otherwise after the decryption one will get an equivalence class representative of $m$ less then $n$.

Decrypt

$m = c^d \bmod n = (m^{e})^{d} \bmod n = m^{ed} \bmod n = m$

Example

$m = 7$ then  $c = 7^7 \pmod{143} = 6$
$m = 6^{103} \pmod {143}= 7$

Notes:

There is also multi-prime RSA where the large prime factors of $n$ are mode than 2.
Textbook RSA is not secure one should never use it without a proper padding scheme. One is the PKCS#v1.5 padding scheme and the other is RSA-OAEP. RSA OAEP has a security proof and PKCS#v1.5 has not. PKCS#v1.5 has many attacks over the years and should not be used.
RSA ( actually any public-key encryption) is not preferable due to the speed. We prefer the hybrid encryption schemes like RSA-KEM for Key Encapsulation Mechanism then encrypt the data with AES-GCM or ChaCha20-Poly-1305 to achieve Data Encapsulation Mechanism, use 256 bit key with AES, preferably.

With this composition of a KEM and a DEM, one can achieve IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack.


What is this EC key derivation method called? I'm looking to identify the EC key derivation method used in Hyperledger Fabric. I can't find anything in the docs or the protocol specs, but the functions' code is here for the private key and the public key.

The derivation function seems to be very simple, DerivedPrivate = MasterPrivate + (k+1) and DerivedPublic = MasterPublic + (k+1) * G all mod N with k being a random derivation data. And yet, I don't seem to be able to find the name or the source of this method.

I'd like to know about the patent and copyright status of this derivation method, and to do that I need something to google for. I'm also looking for a more formal description of this method.

Common terms for this include hierarchical key derivation, hierarchical deterministic keys, and key blinding.  It is sometimes called ‘hierarchical’ because you can repeatedly derive subkeys $Q = [k_1]G + P$, $R = [k_2]G + Q$, etc., and the process is a deterministic function of the tags $k_1$ and $k_2$ and the initial point $P$.  It is sometimes called ‘blinding’ because knowledge of $Q = [k]G + P$ and the standard base point $G$ without the blinding $k$ gives no information about $P$.

You can find practical examples in Bitcoin's BIP32 and related protocols, in the Tor v3 onion service protocol, and in the PrivacyPass protocol.

The two common variants are additive and multiplicative blinding: $[k]G + P$ vs. $[k]P$, both of which are invertible, by $Q - [k]G$ or $[k^{-1} \bmod n]Q$ where $n$ is the order of the group.  The additive variant has the advantage that it always uses fixed-base scalar multiplication, and only a single curve addition, which may or may not make a difference in your protocol.

The analogues in the finite field setting are, of course, $G^k\cdot P$ and $P^k$ with inverses $Q/G^k$ and $Q^{k^{-1} \bmod n}$, but while you'll see this notation in the PrivacyPass paper nobody verbalizes talk of this because while we can say ‘multiplicative’, who can bring themselves to verbalize ‘exponentiative’ without getting distracted wondering whether the word even exists?


How much less secure is an algorithm that gives feedback that the password is one character off? If we had a stupid login procedure (SLP for short) like in this comic; it gives feedback on login, if the submitted password is one character off.

Would a longer password be less secure? What would the break-even point?

If I had a password with length 1, I would always get feedback, that I am one off, so the SLP would not make the password less secure. If I have length 2, I would get feedback half the time, so the SLP would make a password with length 2 as secure as a password with length 1?

The algorithm I would use to hash those password would be:

hash(password)
for(i=0; i++; i < len(password)
  hash(password.deleteChar(i))

For login:

if(hashAndMatch(password)){
  login()
} else {
  for(i=0; i++; i < len(password){
    if(hashAndMatch(password.deleteChar(i))){
      giveFeedBack()
      break;
    }
   }
   error('Wrong password or username')
 }

Let's assume that there are $95$ possible characters for a password. Thus, there are $95^n$ possible $n$ character passwords. You would like for brute force to take on the order of that many guesses to get right, $O(95^n)$.

In your case, given the additional information, once you know you have all characters right except one, it takes only an additional $95$ calls to get the exact password. So, attacking this would take $95^{n-1}+95=O(95^{n-1})$ work.

So, basically it decreases the security by one character.


SECP256K1 Jacobian algorithms I am working on a bitcoin related project and I am trying to speedup the ecc calculation. I started with double-and-add and sliding window.

I would like to go move over to the jacobian coordinates. This is what I found out so far:

Point Doubling

if(Y == 0){
    return POINT_AT_INFINITY
}
S = 4 * X *Y^2
M = 3 * X^2 + a * Z^4
X'= M^2 - 2 * S
y'= M(S - X') - 8 * Y^4
Z'= 2 * Y * Z
return (X', Y', Z')

Point Addition

U1 = X1 * Z2^2
U2 = X2 * Z1^2
S1 = Y1 * Z2^3
S2 = Y2 * Z1^3
if U1 == U2:
    if S1 != S2:
        return POINT_AT_INFINITY
    else:
        return POINT_DOUBLE(X1, Y1, Z1)
H = U2 - U1
R = S2 - S1
X3= R^2 - H^3 - 2 * U1 * H^3
Y3= R * (U1 * H^2 - X3) - S1 * H^3
Z3= H * Z1 * Z2
return (X3, Y3, Z3)

I found out the point at infinity is (0, 1, 0), even I am not sure if this is correct. Since I am not sure about this point, I started to think about the point doubling algorithm. There it checks if Y is 0 and returns the point at infinity. What if the point double algorithm returns the point at infinity and I have to run it again? Y would be 1 in that case and the point doubling algorithm would not detect it.

I know that in affine coordinates this would be a problem but how does it look in Jacobian?

Thanks

Looks like you found those algorithms here?

  I found out the point at infinity is (0, 1, 0), even I am not sure if this is correct.

Yes, you are incorrect about the point at infinity in Jacobian coordinates, which is $\infty = (1:1:0)$. See the answer here for more about that. If $P_1 = -P_2$, you have $P_1 + P_2 = \infty$.

I would highly recommend getting your formulas from the Explicit-Formulas Database in the future, or at least using it as a cross-check. They do a great job  sourcing where their algorithms come from.


public key cryptography and digital signature I read the following from Understanding Public Key Cryptography on Microsoft TechNet:

  Using a private key to establish identity shows that the full
  encryption and decryption operation was accomplished successfully.
  Showing a full operation means that plaintext would have to be
  encrypted to ciphertext using a private key and then decrypted back to
  plaintext using the corresponding public key. If this operation is
  successfully shown, the use of the private key, and only the private
  key, is demonstrated.

  To show a successful encryption and decryption operation, the
  plaintext before the encryption and decryption operations must match
  the plaintext after the encryption and decryption operation. Both sets
  of plaintext must be compared directly and shown to match absolutely.
  There must be a control that is used for comparison and validation.

I'm unable to understand what actually is being said here.

Can somebody please explain this in somewhat simpler terms and with a simple example?

This text tries to explain how digital signatures work, but it actually is a bit misguiding.

It explains digital signatures based on public-key encryption schemes, but this is only valid for schemes like RSA. And even here, you don't simply encrypt some message with your private key to sign it, but you apply the "decryption" operation (i.e. exponentiation with the private key) on a hash of a message, suitably padded.

In RSA, you have a key pair consisting of private key $(n, d)$ and public key $(n, e)$, where $n$, $d$ are quite big numbers (the size of $n$ relates to the security of the scheme), $e$ usually a smaller number like $2^{16}+1$.

In the "textbook version" (without any padding/hashing), to sign a message $M \leq n$, you calculate $s := M^d \bmod n$, where $\bmod$ is the integer remainder operator. The pair $(M, s)$ is then the signed message.
To verify the signature, anyone can calculate $M' := s^e \bmod n$ and then check if $M \mathrel{\overset?=} M'$. Here signing looks like RSA-encrypting with the private key and verifying looks like RSA-decrypting with the public key, which is the reason that the article tries to show it as such.

The real RSA-based signature schemes work a bit different: We apply a one-way hash function $H$ and a semi-random padding $P$ on the message before the exponentiation, so the signature is $s := P(H(M))^d \bmod n$, and this can be checked as $P^{-1}(s^e \bmod n) \mathrel{\overset?=} H(M)$ (where $P^{-1}$ also checks if the padding was really correct). This hashing and padding actually makes the scheme secure against forgeries (and it also allows to sign messages longer than $n$).

There are other signature schemes which do not relate directly to an encryption scheme, for example DSA.

To use a digital signature for authentication (or "identity verification", as the article says), you normally don't sign an arbitrary message, but you sign a piece of data which is somehow relevant to the protocol. For example, in the SSH protocol, at the end of a Diffie-Hellman key exchange, the server signs about everything important which was exchanged, to make sure that there was no man-in-the-middle attack which modified the exchanged data.


Why is Min-entropy significant in cryptography? Let $H_{min}$ = Min-entropy and $H$ = Shannon entropy.

Unless you're gaming the system or deliberately trying to be obtuse, very rarely is $ \frac{H}  {H_{min}} > 10$ from any conceivable physical source. To achieve a ratio of >10 in hardware/ real life would be quite a feat of engineering and tantamount to a joke/NSA conspiracy.  For  worldly context, lift engineering commonly uses a safety factor of 7.  If the lift gear fails, real people die. Since arbitrarily, $ \frac{H}{100} << H_{min} $ in the overwhelming majority of cases, why is $H_{min}$ significant in cryptography?

I know the definitions.

In most cases, cryptography requires values to be uniformly random (in which case discussions of min-entropy are moot) or unpredictable (in which case min-entropy isn't sufficient --- though "conditional" min-entropy might be --- since in these contexts an adversary typically has multiple guesses).

The context where I see min-entropy play the greatest role is in randomness extraction. Since physical sources of randomness rarely produce uniformly random bits, we need a way to transform the output of some physical system (presumably containing some amount of entropy, however measured) into a uniformly random bit string. At that point, we can start to do cryptography.

The Leftover Hash Lemma tells us how to take an input $X$ and transform it into a value $f_S(X) \in \{0, 1\}^n$ that is "close" to uniform. In particular, it tells us how to construct $f$ such that $n \leq H_{\infty}(X) - 2 \log(1/\epsilon)$, where $\epsilon$ is the statistical distance between the uniform distribution and $f_S(X)$ (technically, the distance between $(S, f_S(X))$ and $(S, U)$, where $U$ and $S$ are uniform and $S$ is implicitly a fixed, public value).

We're not making any assumptions on $X$ except for it's min-entropy. This quite nice because in practice we can't precisely characterize the distributions used to provide inputs to RNGs (which vary from device to device in the case of HW RNGs, and are not known a priori in the case of, e.g., /dev/urandom). Of course, estimating $H_{\infty}(X)$ is its own bag of worms...