Why use argon2i or argon2d if argon2id exists?

The current Argon2 draft RFC, I think, provides a good, reasonably brief answers to this question.  TL;DR: most people will indeed want to use Argon2id and not the "pure" variants.

The introduction summarizes the issues quite well:

  Argon2 has one primary variant: Argon2id, and two supplementary variants: Argon2d and Argon2i.  Argon2d uses data-depending memory access, which makes it suitable for cryptocurrencies and proof-of-work applications with no threats from side-channel timing attacks.  Argon2i uses data-independent memory access, which is preferred for password hashing and password-based key derivation.  Argon2id works as Argon2i for the first half of the first iteration over the memory, and as Argon2d for the rest, thus providing both side-channel attack protection and brute-force cost savings due to time-memory tradeoffs. Argon2i makes more passes over the memory to protect from tradeoff attacks.

Basically, there are two kinds of attack considered:

Side-channel timing attacks.
Time-memory tradeoff (TMTO) attacks.

Argon2d is vulnerable to timing attacks, but offers the best resistance to TMTO (section 9.2):

  The best tradeoff attack on $t$-pass Argon2d is the ranking tradeoff   attack, which reduces the time-area product by the factor of 1.33.

Argon2i is invulnerable to side-channel timing attacks, but is weaker against TMTO:

  The best attacks on the 1-pass and 2-pass Argon2i is the low-storage   attack described in [CBS16], which reduces the time-area product (using the peak memory value) by the factor of 5.  The best attack on 3-pass and more Argon2i is [AB16] with reduction factor being a function of memory size and the number of passes.  For 1 GiB of memory: 3 for 3 passes, 2.5 for 4 passes, 2 for 6 passes.  The reduction factor grows by about 0.5 with every doubling the memory size.  To completely prevent time-space tradeoffs from [AB16], number $t$ of passes must exceed binary logarithm of memory minus 26.

Argon2id sits in between:

  The best tradeoff attack on 1-pass Argon2id is the combined low-storage attack (for the first half of the memory) and the ranking attack (for the second half), which bring together the factor of about 2.1.

Since the Argon2 runtime grows linearly with the number of passes, Argon2i with six passes is about six times as slow as Argon2id with one pass.

The draft RFC also states (without explanation) that Argon2id resists timing attacks, and recommends it as the primary variant, and explicitly telling you (section 4, "Parameter choice") that if you don't know which to use, you should pick Argon2id.  You should probably wait until the RFC is approved to fully commit to anything, but in the meantime if you're writing some early code it makes sense to bias things in favor of Argon2id.


It looks like you want a message authentication code (MAC).

A MAC is a computable function $M$ of two inputs $k$ and $x$ (usually with variable-sized $x$ and fixed-sized $k$ and output) such that:

Given a lot of pairs $(x_i, m_i)$ with $m_i = M(k, x_i)$ (and not given $k$), it is hard to find $(m, x)$ with $m = M(k, x)$ and $x$ is not one of the $x_i$s).

You actually only need a slightly weaker condition:

Given a lot of pairs $(x_i, m_i)$ with $m_i = M(k, x_i)$ and an $x$ which is not one of the $x_i$s (and not given $k$), and it is hard to find $m = M(k, x)$.

While a random oracle with simple concatenation of the inputs (in either order) would do fine as a MAC, real-life hash functions are not random oracles.
Thus we usually use specially-made MAC functions for this goal - there are ones based on hash functions (specifically HMAC which can be instantiated with every hash function), and others based on block ciphers.

It might be that SHA-256 is safe anyways (maybe depending on the length of your strings), but this is not what SHA-256 was made for.

Simply use HMAC-SHA-256 instead (with your $X$ in the key position).


The following information about the DES S-Box might be useful (taken from here):

DES Design Criteria

there were 12 criterion used, resulting in about 1000 possible S-Boxes, of which the implementers chose 8

these criteria are CLASSIFIED SECRET

however, some of them have become known

The following are design criterion:
R1: Each row of an S-box is a permutation of 0 to 15
R2: No S-Box is a linear of affine function of the input
R3: Changing one input bit to an S-box results in changing at least two output bits
R4: S(x) and S(x+001100) must differ in at least 2 bits
The following are said to be caused by design criteria
R5: S(x) [[pi]] S(x+11ef 00) for any choice of e and f
R6: The S-boxes were chosen to minimize the difference between the number of 1's and 0's in any S-box output when any single input is held constant
R7: The S-boxes chosen require significantly more minterms than a random choice would require

For Rijndael, things were different as the S-Box in Rijndael had to meet certain requirements mathematically and cryptanalytically


How secure is the E0 stream cipher used in Bluetooth?

Bluetooth has gone through a few transitions in protocol.  Bluetooth BR/EDR uses E0/SAFER for a cipher and Bluetooth LE uses AES-CCM.   Fundamentally, when you write a specification as an engineer, you are looking for a minimally viable CMOS implementation.  You make choices that are not always the best from a cryptographic standpoint because you have space or power constraints.  For instance, AES is rather large compared to some stream ciphers and I believe the motivation of using E0 was die space because LFSRs are smaller than an AES implementation.  I personally use SIMON over AES in hardware because it's smaller, faster and lower power in a CMOS implementation, and this is particularly true when you are encoding a "bit stream", such you'll have in RFID or Bluetooth.

I know from being in a meeting that FIPS-140 validation for Bluetooth was an important conversation with the Bluetooth LE spec, which is why AES was added.  I can only assume that AES was not used in the original ICs due to cost on the hardware side.  Looking at 130nm dies (so, back in the day), AES would cost me about 0.03 USD in area.  Just by guessing the area of E0, I would say it's 0.01 USD, so it must have mostly been an economic consideration during the time of early adoption.

E0 itself is not particularly secure and is vulnerable to known plaintext attacks.


Identification of correct plaintext after decryption in Rabin cryptosystem

This is a solution that should work with very high probability, but possibly can fail. As a bonus it also resists tampering with the ciphertext.

As encrypter generate a random key (say a 128-bit key for AES128-CTR) and encrypt the plaintext using that key. Then compute a MAC over the ciphertext (for example using HMAC-SHA1) using the same key. Finally you encrypt the randomly generated key using the Rabin cryptosystem. You then send $encrypted\_key || MAC || ciphertext$ to the receiver.

The receiver first decrypts the encrypted key to get 4 potential keys. For each key he computes the MAC over the ciphertext and see if it equals the sent MAC. If yes he proceeds to decrypt the ciphertext using that key.

Another bonus of this system is authentication. If you have a shared secret/token of sufficient cryptographic length (say 128 bits) between sender and receiver you can use that as the key for the MAC instead of the randomly generated key.


FFX is not malleable. It's a strong tweakable pseudo-random permutation, where the "strong" here indicates that both encryption and decryption look like random permutations from the attacker's perspective. In particular, there's no relationship between the plaintexts of closely related ciphertexts (aside from the trivial observation that different ciphertexts give different plaintexts).

FFX can provide integrity protection in very limited circumstances. If most plaintexts aren't valid, then you can detect tampering by ensuring that the plaintext is valid upon decryption. (This is not true for encryption in general --- it's another feature of algorithms with strong tweakable pseudo-random permutation security.) For example, if the plaintext contains a checksum, as with a credit card number, then validating the checksum provides some degree of integrity. However, in most cases this isn't a very strong check; a single-digit checksum will allow one in ten forgery attempts to succeed. (See "Encode-then-encipher encryption" by Bellare and Rogaway as well as the RAE definition in "Robust Authenticated Encryption: AEZ and the Problem it Solves" by Hoang, Krovetz, and Rogaway.)


If we have multiple unique RSA signed messages produced from the same private key, can we always find new valid signatures?

For $t$ signatures, I think we can have at most $\sum_{i=2}^{t}\binom{t}{i}$ new signatures. Is this correct?

That's the number of new (message, signature) pairs with message of the form $\prod m_i^{k_i}\bmod n$ with $k_i\in\{0,1\}$ and $1<\sum k_i$; that is, we combine at least two existing messages. BTW, that simplifies to $2^t-t-1$.
But we can just as well compute the signature for message $\prod m_i^{k_i}\bmod n$ for any integers $k_i$. As noted in the question, $k_i=-1$ or more generally negative works too. And even more generally, we can compute as many (message, signature) pairs as we see fit if we know $(n,e)$, for we can find the message matching any desired signature, by raising the signature to the power $e$ modulo $n$. Problem from an attacker's perspective is that the messages thus obtained are largely random-like.
Conclusion: textbook RSA signature can be secure only if the parties that verify are selective in the messages they accept, and the signers selective in the messages they sign. That's where message padding for RSA signature comes to play.

Are inverses necessary to produce new signatures?

No. That's one of the tricks that can be pulled to form new (message, signature) pairs with specific properties of the message in attacks against some RSA signature practices.


There is a very interesting paper that relates to this exact question (but you wouldn't guess it from the title). The paper is titled Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. In Section 3, the paper considers the multiple encryption problem and gives novel attacks that are better than what you would expect (for a general multiple encryption $r$ times). For example, for 2DES there is an attack taking about $2^{56}$ time and $2^{56}$ space. You would therefore expect that 4DES would give you $2^{112}$ time and $2^{112}$ space. However, they show an attack that takes time $2^{112}$ and only space $2^{56}$.

In any case, in practice there is no good reason to use this. You are far better off using AES. DES's block size is too small, and it is very slow as it is (repeating 4 or 5 times will completely kill you).


How to use HMAC-SHA1, HMAC-SHA2 in conjunction with AES

Is the calculated MAC encrypted using AES? What is the purpose? How
  about signing and verifying? How does AEs Play a role here? Is the
  case here that the encrypted AES is HMACed for signing and the HMAC is
  verified

No, the MAC is not encrypted per se, however, it is calculated in conjunction with a key (independent of the encryption key).

Simply encrypting your data ensures privacy, however, it doesn't ensure integrity (ie, that the ciphertext hasn't been tampered with since it was encrypted). Using a HMAC provides this integrity.

A simple hash function by itself is not sufficient, as an attacker could alter the ciphertext, calculate a new hash, append it to the new ciphertext, and you would be unable to detect any tampering.  A HMAC solves this problem as it uses a key - meaning that an attacker is unable to create a valid HMAC unless they have a valid key (which only you possess).

You should note that if you plan to encrypt-then-HMAC, you not only need to calculate the MAC of the ciphertext, but also the IV ...ie, HMAC((ciphertext+IV), key)

You should also note that independent keys should be used for the encryption (AES, for example) and the authentication (HMAC).  One approach is to use a masterkey, and then derive two separate keys using a KDF.

Of course, using an authenticated encryption mode such as GCM or EAX is less prone to implementation errors (assuming you're using a well-vetted library), and is recommended if you don't have much experience in crypto.


NewHope is a key-exchange protocol based on the Ring-Learning-with-Errors (Ring-LWE) problem. NewHope512-CCA-KEM and NewHope1024-CCA-KEM are IND-CCA-secure key encapsulation mechanisms which target level 1 and level 5, respectively, (matching or exceeding the brute-force security of AES-128 and AES-256, respectively). Google is working on deploying post-quantum key-agreement in TLS by combining NewHope with an existing key-agreement (X25519)as the combination CECPQ1. Please find a GoLang implementation of NewHope in GitHub.


Why are digital signatures used when performing DH?

In principle, if the server has a long-term secret exponent $s$, and a long-term public point $S = g^s$ that the client is willing to believe, then that's enough for the client to send a confidential authenticated message to the server: client picks $c$ at random, computes $C = g^s$, computes $k = H(S^c) = H(g^{sc})$, and uses $k$ as the key for symmetric authenticated encryption.

Unlike a signature, there's no third-party verifiability; anyone who can verify the conversation's authenticators can also forge them.  If you want fast key erasure, then you can use this authenticated channel to perform an ephemeral Diffie–Hellman key agreement, as, e.g., the Signal protocol (technical documentation) does.

Why didn't we do this in, e.g., SSH and TLS?
Mainly for hysterical raisins, I expect.  The use of signatures in TLS goes back to the original SSL, where I'd guess it was derived from the use of signatures in x.400 email with x.509 certificates.

For a certificate chain, you need a signature because you need third-party verifiability, and when you already have an authentication hammer, why bother devising another public-key authentication mechanism?  Symmetric authenticators, i.e. MACs, as needed by a public-key authenticator using DH, were not really popular until the mid-nineties when HMAC was developed, even though the concept was first published in 1974.

Why don't we do this now in, e.g., SSH and TLS, using the public keys in certificates that are already deployed?
Many of them are RSA keys that are fit only for signature or (nonephemeral) key agreement, as in RSA key agreement, not for ephemeral Diffie–Hellman key agreement.*  There technically are standards for x.509 certificates for static Diffie–Hellman public keys, but these are seldom used.

Why don't we use this in any protocols?
Well, we do.  Public-key authentication without nonrepudiation didn't become popular until OTR in 2004, though proposals for it to replace email signatures date back to 2000.  The dnscurve protocol was designed around fitting a server's long-term X25519 public key in a tagged DNS label so that you can compatibly fit it into a standard NS record.  The Signal protocol uses long-term DH keys for authentication extensively.  The Noise protocol framework doesn't use signatures at all at the moment; all authentication is via long-term DH keys.

Why don't we retroactively use it for protocols that already have Ed25519 keys deployed for signatures?
We could, e.g. using XEdDSA, but someone would need to implement it to make it happen.  I can't speak for all protocols out there!  Will you send the patch to OpenSSH to implement public-key authenticators using XEdDSA for deployed X25519 keys, and argue on the mailing list to justify the additional complexity, when signatures already work?  When you design a new protocol, will you use long-term DH keys for authenticators instead of signatures?

Note, of course, that merely using long-term DH keys for authentication doesn't allow key erasure because the keys are, well, long-term.  So for fast key erasure, you still have to compose it with ephemeral DH keys, as I summarized in a recent post on an idealization of how WhatsApp works.

* Here ephemeral means that the keys can be erased after a session and all its resumption tokens have been erased, so compromise of the server's long-term identity key doesn't enable retroactive decryption of past sessions.  This property is sometimes called forward secrecy, a term that glibly obscures when the erasure happens, which is particularly important to take care of with TLS resumption tokens.


Understanding elliptic curve point addition over a finite field

Your coordinates are elements of the finite field. For a point $P = (x_p, y_p)$ with $x_p,y_p \in \mathbb{F}_n$, where $\mathbf{F}_n$ is the finite field of order $n$ over which the elliptic curve is defined.

Since $n$ is prime, your slope will also be an element of the field $\mathbb{F}_n$. Even if $n$ was composite and $\gcd(x_q - x_p, n) = 1$, $\lambda$ is still an element of your field since an inverse of $(x_q - x_p)$ would still exist in this case. To compute the slope, you must find the multiplicative inverse of $(x_q-x_p)$ in your field $\mathbb{F}_n$. Then
$$\lambda \equiv (y_q - y_p)\cdot(x_q - x_p)^{-1} \pmod n \text.$$


Zero Knowledge Proof extended Schnorr - average secrets

Here is a protocol that seems to fit your requirements: Let P be a prover and V be a verifier. $g_1,g_2,g_3$ are all generators of a group of order $p$ in which the discrete logarithm cannot be solved efficiently (note: you don't need Diffie-Hellman to be hard, discrete log is sufficient). (I assume that neither P nor V know the discrete log of $g_i$ in base $g_j$ for $i \neq j$).

Both players know three group elements $C_1,C_2,C_3$. First, P sends a value $a$ to V, which is the sum of the $num_i$ (this is perfectly equivalent to giving the average). Now, P intends to prove to V that he knows $(id_i, num_i,r_i)_{i\leq 3}$ such that $C_i = g_1^{id_i}g_2^{num_i}g_3^{r_i}$ for $i\leq 3$, and $a = num_1 + num_2 + num_3$.

Note: it is important to remark that this can only be a proof of knowledge of such values, and not a proof of their existence, as for any triple $(C_1,C_2,C_3)$, there exist many values satisfying your requirements.

Protocol:

P picks nine random exponents $(x_i,y_i,z_i)_{i\leq 3}$, with the constraint that $y_1+y_2+y_3 = 0 \bmod p$, and sends $(R_i)_{i\leq 3} = (g_1^{x_i}g_2^{y_i}g_3^{z_i})_{i\leq 3}$ to V.
V sends a random challenge $e \leq p$ to P.
P sends $(u_i)_{i\leq 3} = (e\cdot id_i + x_i \bmod p)_{i\leq 3}$, $(v_i)_{i\leq 3} = (e\cdot num_i + y_i \bmod p)_{i\leq 3}$, and $(w_i)_{i\leq 3} = (e\cdot r_i + z_i \bmod p)_{i\leq 3}$.
V checks that $C_i^{e} R_i = g_1^{u_i}g_2^{v_i}g_3^{w_i}$ for every $i \leq 3$, and that $v_1+v_2+v_3 = a\cdot e \bmod p$. He accepts if all the checks pass.

This is an honest-verifier zero-knowledge proof of knowledge of $(id_i, num_i,r_i)_{i\leq 3}$ such that $C_i = g_1^{id_i}g_2^{num_i}g_3^{r_i}$ for $i\leq 3$, and $a = num_1 + num_2 + num_3$ (hence, assuming the verifier behaves honestly, it reveals nothing about all those values, except that this statement is true). The average value is then just $a/3$. The protocol can be enhanced into a truly zero-knowledge protocol (which remains zero-knowledge even if the verifier is dishonest) using classical techniques (for example, by letting V send an extractable commitment of $e$ before the first flow of the protocol). It can also be made more efficient regarding communication, using batch techniques.

This is a quite classical example of a zero-knowledge proof of knowledge of discrete logarithms in multiple basis, satisfying some relations. The fact that the protocol is correct is easy to see from its description (if the prover is honest, then the proof is accepted). Proving that it is sound (the prover cannot cheat and make the proof pass without knowing such values) requires the use of a technique called rewinding (to show that if the proof pass, some simulator could extract the values by interacting with the prover, which shows that the prover know those values). Proving that it is (honest-verifier) zero-knowledge is done by showing that if the prover knows $e$ in advance , he can pass the proof even without knowing such values. However, writing the full proof formally would be a bit extensive here. Such proofs require to be already quite familiar with zero-knowledge proofs.


Are there known special cases where the first 160 bits of keccak256 can be null ? Or does finding a collision is required?

No. SHA-2, Keccak, and serious alternatives to those two are all assumed to be model-able as a random oracle. Given an valid input it will return back a bit string chosen from a uniform random distribution.

The probability of any one such string starting with an all zero 160 bit prefix is $2^{-160}$. That's too small to find by chance. The amount of work to search for such a string should therefore be about equivalent to $2^{160}$ hash evaluations. That would consume a lot of time and a lot of power. So much so that it's impossible for any of us Earthlings to acheive.

If there is a way to search for inputs whose outputs have a certain property which is faster than by brute force, then that means the algorithm is broken. An attack that lets you easily find inputs that result in output bits set to a certain value is called a (partial) preimage attack.

Edit: I answered only the cryptography part of the question. Not the cryptocurrency. That's off topic for this site. Also off topic is the contract code. There could be some subtle (or obvious) problem in the code that causes problems or enables scams. Maybe there is some type conversion rule that mixes up zero values, null pointers, none-value. Maybe errors propagate as null pointers or zero return values. Do not interpret my not covering non-cryptography material as endorsement of a product.


To supplement the other answer, I will show that the proposed scheme cannot be shown secure assuming only collision resistance of the hash function. (I.e., the  standard assumption on hash functions.)

Let $H' : \{0,1\}^* \to \{0,1\}^{\ell-1}$ be a collision resistant hash function. We construct another hash function $H : \{0,1\}^* \to \{0,1\}^{\ell}$ as follows:
$$ H(x\|b) := H'(x)\|b,$$
where $b$ denotes the last bit of the input.

It is easy to see that $H$ must be collision resistant whenever $H'$ is collision resistant. This is because any collision in $H$ trivially (and by construction) must also yield a collision in $H'$.

If you, however, instantiate your proposed MAC construction with $H$, we end up with a scheme that is existentially forgeable under a known message attack. Suppose an adversary receives a message $m$ and a tag $t=H(k\oplus m)$.

Let $k = k'\|b_k$, $m=m'\|b_m$ $t=t'\|b_t$ where $b_k,b_m$ and $b_t$ are bits. Then by construction of $H$ we have

\begin{align*}
t=&\ H\bigl((k'\|b_k) \oplus (m'\|b_m)\bigr)\\
=&\ H\bigl((k'\oplus m') \| (b_k\oplus b_m)\bigr)\\
=&\ H'(k'\oplus m')\|(b_k\oplus b_m).
\end{align*}

This means, that the adversary can simply output $m^*=m'\|(b_m\oplus 1)$ and $t^*=t'\|(b_t\oplus 1)$ as a forgery. This will verify, since

\begin{align*}
H(k\oplus m^*)=&\ H\bigl((k'\|b_k) \oplus (m'\|(b_m\oplus 1))\bigr)\\
=&\ H\bigl((k'\oplus m') \| (b_k\oplus b_m\oplus 1)\bigr)\\
=&\ t'\|(b_t\oplus 1).
\end{align*}


Why is the salt used only once in PBKDF2, while the password is used often?

Summary: I don't know of any good reason why it has to be this way. In practice, I don't think it is necessary to inject the password into every iteration.  As far as I know, I think the construction would still be secure (in practice) if you used the salt and password only in the input to the first iteration, and then just repeatedly hashed the result many times without feeding in the password any further.

So why does PBKDF2 do it, if it is not strictly necessary for security?  I don't know.  I can only speculate -- and you should take my speculation with a large grain of salt.  That said, my speculation is that, by using the key in every iteration, you can get some slightly better provable-security results.

Technical speculation: it has to do with the security proof.  In particular, with PBKDF2, it is possible to prove a statement along the lines of: if HMAC-SHA256 is a secure PRF, and if the password is a full-entropy full-strength crypto key, then PBKDF2(password, salt) is a secure cryptographic key.  No such statement would available if every iteration after the first used a bare hash instead of a HMAC PRF; you'd need to make stronger assumptions, such as work in the random oracle model (i.e., assume that the hash is perfect in every regard).

That said, the difference in provable security feels rather negligible to me.  The security claim that you can prove about PBKDF2 (without the random oracle model) is not very exciting.  PBKDF2 is primarily used to derive keys from a memorable password that is not full-entropy, and that situation is not covered by the security proof above.  So, as far as I can see, I don't know of any compelling reason why PBKDF2 was designed to inject the password into every iteration of the algorithm.

Standard disclaimer: don't roll your own. Please don't take this post as a justification for modifying PBKDF2 and using your modified version of PBKDF2.  That would be a pretty risky thing to do.  Even if we can't think of any strong reason why PBKDF2 had to be designed the way it did, it's still safer to use the standard primitive.  PBKDF2 has been well-vetted, and who knows, maybe there's some problem with the variant that hasn't occurred to me.


How can I quickly generate thousands of letters randomly, and strongly mitigate the risk of any compromise?

Upon careful reflection, I suggest the following three alternatives. They are in increasing order of effort.

1.

Get the 4000 bytes from a blocking implementation of \dev\random. That will generate information theoretic secure output within an hour of computer usage as the entropy will come from your mouse and key strokes. You won’t have to do anything other than use the machine. So you type:-

 dd if=/dev/random of=my_letters bs=1 count=4000 iflag=fullblock

and keep surfing/typing till it completes and the random characters appear in my_letters. This took   37 minutes on my machine. Inclusion of an entropy collector like HAVEGE will help greatly, but I don't entirely trust the entropy rate estimation for it.

Stuff about dd here. Caution: dd is short for 'disc destroyer'.

Note. In TAILS, dev/random = dev/urandom and therefore unsuitable for OTP generation.

2.

Take 63 photos a blank wall in a very dark room. This seems like a lot, but isn’t.  It’s just 63 consecutive presses of the shutter. Say 5 minutes.  Try to get the lighting so that the entire view finder is illuminated i.e all pixel values > 0. If you have ISO control, turn that up to the max. It's 99% pure entropy from the many types of noise within all CMOS camera sensors. The cheaper the camera, the better. You simply consider the JPEG encoding of the sensor's image as the post processing component of NIST's generic TRNG architecture, as:-

You then treat it as a bit fixing, block entropy source.   There will be no semantic content within the image, so it's just the efforts of the JPEG algorithm to capture the noise. And that's essentially quantum noise, just like the best laboratory phase based TRNGs.  Typically I would then measure it's entropy with a compression algorithm like cmix, but that'll take hours (so I haven't), and you only need 4000 bytes. You can be confident that the image contains >> 4000 bytes of entropy within any decent camera frame as there's nothing else. The piling up lemma will deal with that. You don't have to open the image raster, just use the raw .jpg.

And then use your favourite programming language to do $  \operatorname{SHA-512}(jpg_i) $ in a loop of 63 file hashes and concatenations. Or do cat jpg_i | sha512sum >> my_letters 63 times which is not as monotonous as it sounds with automatic consecutive image numbering and command recall.

This online TRNG uses this technique.

3.

Acquire a Zener diode (<£3) , some batteries and a hammer.  Don’t laugh – it works perfectly. Build something like:-

and plug it into an Arduino’s analogue to digital converter.  There will be lots of quantum Avalanche noise created (>1Vpp). The Arduino then just forwards the raw samples to a PC for you to follow the hash based extraction procedure described above. This time you’ll have to use cmix (or equivalent) to measure the entropy rate to ensure that you’re hashing more than 1024 bits of entropy. That's to be in lock-step with NIST’s definition of ‘full’ entropy.  I use a safety factor of 3, so hash 3072 bits each time. A little C programming will be required, but Arduino’s are used in schools.

cmix details here, and it's greedy for RAM.

I recommend option 1 for zero effort, but option 3 for maximum fun. And option 3 is not limited to 4000 characters of course.


Is it safe to reuse the password when using AES-CTR with scrypt?

CTR is insecure if you reuse a key/iv pair. Since the salt is random, a different encryption key will be derived every time you encrypt something. Therefore it is safe even if it always uses the zero IV. Of course, the password must be strong enough to resist brute force attacks.


Is the assumption that AES is "best" a valid one, alongside the assumption for AES_GCM?

Opinionated, but Microsoft doesn't implement a lot of modern ciphers, so AES is the tried and true one. If GCM mode is best depends on the use case really, but as it is an authenticated mode - it includes a MAC - it is generally better than e.g. ECB / CBC which aren't.

Is ECDSA actually an encryption algorithm, given the name?

Asking the question is answering it: no it is not. However, using ECIES, you can use the keys both for ECDSA and ECDH, and ECDH enables ECIES, which is an encryption scheme.

Why do the UWP API asymmetric encryption algorithms all reference signing with hashes in their descriptions? Is this really the case, and if so why? Surely if they wanted authentication through signing it would be a separate process?

I don't know, Microsoft webpages are down, I get a 403. Oh, they are up again, and they are as helpful as ever. Off topic here though.

Is OAEP generally considered better than PKCS#1?

PKCS#1 v2.0 is the standard that defines OAEP, so that's a nonsensical question if you take it literally. Yes, generally it is considered more secure than PKCS#1 v1.5, which is what "PKCS#1" usually refers to. Although you could say that this is opinionated as well, at least OAEP has got a proof that it is secure given that RSA is secure.

What is the difference between the ECDSA algorithms which do and don't specify public key size (eg ECDSA_SHA256 vs ECDSA_P256_SHA256)?

That's more of an issue with the API, maybe the P256 one assumes the Certicom named curve with the NIST standardized name. Again, not specified.

What difference do the hash sizes (and public key sizes for ECDSA if relevant) make, and what about if authentication isn't needed (which I guess would be why they're hashing and signing in the first place).

Hashes are used for a lot of things, e.g. OAEP uses them internally as well, but not to authenticate the message. In ECDSA they are used to hash the message, which is then used in signature generation and verification. Generally a larger hash output size / key size means more secure.


No, that does not work for ElGamal. If you look at ElGamal encryption and signatures you will see that they are fairly different.

That works for RSA because RSA is commutative, i.e., $f_{d,n}(f_{e,n}(m))=f_{e,n}(f_{d,n}(m))$ for all $m\in Z_n$ holds, where $f_{e,n}(m):=m^e \mod n$ is the enryption function and $f_{d,n}(m):=m^d \mod n$ the decryption function. You can easily convince yourself that this holds.

That is the reason for why there exists the bad practice oft teaching signatures as "encrypting with the private key" for signing and "decrypting with the public key" for verification, since the above holds for RSA and people tend to generalize that. But thats not the general case, and, as said,  is a bad practice.


In your signature each signer only seems to add their secret $a$ in once. An attacker who could get someone to sign first $M_1$, then $M_2$ and finally both as a set could find $a = S_1 + S_2 - S_{12}$ $mod$ $l$, i.e. all but a few bits of the secret $a$, the rest being within easy brute force search.

Not sure if that's your only problem.


AES Is it safe to expose the plaintext and cyphertext in the same place,

Use a message authentication code if you want to ensure that the id is not modified by the client. Use SSL between the server and the client if you want to prevent replay etc network layer attacks from eavesdroppers.

But a malicious client can still reuse previously received ID. If this is a concern, you need to do more (e.g. use and keep a nonce for verification).


Two files encrypted with related data versus one file

No, it doesn't lower security, but it doesn't (asimptotically) enhances it either.
AES (or better, as Thomas pointed out, the way aes is used inside Truecrypt) is secure against IND-CPA attacks, so the encryption of a file itself does not reveal ANY information about the plaintext, except for its length.

Even if an adversary knows 99 bits of a 100 bits encrypted file (but not the encryption key), it cannot find the last bit without iterating trough the whole set of keys.
Knowing something about the plaintext does not help the adversary.


Why does EdDSA require a b-bit private key instead of b/2-bit?

One possible reason (and probably the one that was behind that design choice) is to avoid multi-target attacks.

Consider a setup where there are $k$ public/private key pairs, and the attacker's goal is to find one of these private keys. The attacker does not care which private key is obtained; getting any of them is a "win". For instance, the attacker wants to make a fake X.509 certificate by recovering the private key of a certificate authority: any private key in a chain to any root CA in the set of trusted root CA will do. A brute force attack on the $b$-bit seed will succeed with average cost $2^b/k$ (the attacker computes the public key for each potential $b$-bit seed, then looks up the public key in the set of targets; the looking-up does not involve complicated maths and can be done in "negligible" time, compared to the computation of the public key). If $b = 128$ and $k$ is large, then this can be substantially less than $2^{128}$.

From an "academic" point of view, this means that 128-bit seeds only provide "64-bit security": if there is a set of $2^{64}$ targets, then the attack succeeds in cost $2^{64}$, while the defenders collectively spent an effort of only $2^{64}$. Bumping seed size up to 256 bits is an easy and inexpensive way to prevent that kind of academic break.


Why doesn't this dummy mutual authentication protocol provide mutual authentication?

I think you've got all the right ideas but I think you're lacking an understanding about how Public Key Cryptography works.

Trudy can only impersonate Alice in this scenario with a replay attack (or if some kind of authentication credentials are returned...like an http cookie, Trudy could steal that too). Since she does not have Alice's private key, she can only successfully respond to Bob's challenge by waiting for Alice to respond and stealing response. In this simple scenario, Bob will be unable to tell if Trudy sent the message or if Alice did.

In reality, Bob and Alice have everything needed to create a secure protocol. Because Bob and Alice have the capability to verify the message was sent (using eachother's public keys), they can also encrypt messages only the other can decrypt. Bob can sign his challenge he has generated, encrypt this using Alice's public key, and then send it all to Alice.

Alice then decrypts, verifies Bob sent it using his public key, and can generate the response, sign it, and encrypt the same way Bob did.


Prove that this protocol based on square roots modulo $n$ is zero knowledge

Here's the simulator $S$ to replace $P$ for challenge $y = x^2 \mod n$:

Choose $a$ randomly from $\mathbb{Z}_n$, draw a bit $b'$ uniformly.
Send $a^2 y^{-b'} \mod n$ to $V$. The inversion is done in $\mathbb{Z}_n$ of course.
$V$ replies with $b$:

If $b = b'$: send $a$ to $V$
Otherwise: abort

If $b'$ is drawn uniformly, then it doesn't matter how $b$ is chosen - the simulator always has exactly probability $0.5$ for the case $b = b'$ for a successfull verification.


Let's say we have a message (sent by Person A) encrypted with CBC using the IV $x$, and the first block of the message is either "Yes" or "No".  We also assume the attacker has the capability of requesting the encryption of arbitrary chosen plaintexts (though he doesn't control the IV - it is always incremented after each encryption request).  Let us also say the IV is predictable by the attacker (an incremented IV is predictable so long as the attacker always knows and/or can control when the encryption function is used).  In other words, the attacker knows that if he requests the encryption of some plaintext then the IV used to encrypt it will be $x \oplus k$ for some value $k$.  Let's denote the IV the attacker predicts will be used if he makes a request by $IV_z$ ("z" for Person Z), i.e. $IV_z = x \oplus k$.

In which case the attack is simple: Request the encryption of a plaintext where the first block is "Yes" $\oplus$ $k$.  Because of how CBC works, the first block of ciphertext, $C_z$, will be: $C_z = E(Yes \oplus k \oplus IV_z) = E(Yes \oplus k \oplus x \oplus k) = E(Yes \oplus x)$.

Now the attacker compares $C_z$ to the first block of the encrypted message sent by Person A, which we will denote as $C_a$.  If the message sent by Person A started with a "Yes" then $C_a = E(Yes \oplus IV_a) = E(Yes \oplus x)$.  So if the message started with "Yes" then $C_z = C_a$.  Conversely, if the message started with "No" then $C_z \neq C_a$.  So simply by comparing $C_z$ with $C_a$ the attacker can easily determine the first block of the message.


Warding an ECIES setup against MitM: ECDSA?

Yes, if you want to protect the message you could use sign-then-encrypt or sign-then-encrypt-then sign to provide authenticity and integrity. Without it an attacker may change the bits of the ciphertext, or simply create an encrypted message.

ECDSA would be the logical choice if you're already using ECIES. It may still be a good idea to use separate keys for signing and encrypting though (if just because you need the keys on different occasions).

You need to trust the public key of the other person before signing or encryption makes any sense though. It's OK not to trust a CA, but in that case you need a different way of performing key management within your PKI.

You could use separate channels to confirm key fingerprints, you could use a web-of-trust, share keys by sneakernet (memory sticks) whatever. But if eavesdropping is possible then 9 times out of 10 so are MitM, so you should make sure that an attacker cannot substitute the public key with their own public key.


How can we define post-Quantum Cryptography?

You pretty much included a relatively accurate informal gist in the sentence before this question:

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario.

The more interesting question follows:

What is the specification that makes it somehow impossible to break?

First a minor clarification: few algorithms are impossible to break in a conceptual sense - worst case scenario, guessing the key is always a viable strategy (the exceptions are one-time-pads and the analogous one-time authenticators). So it's a matter of cost rather than possibility, namely how much time it would require to defeat the system (space can also play a role in addition to time).
Post-Quantum cryptography usually refers to asymmetric algorithms (key agreement, public key encryption, and digital signatures) that are not known to be vulnerable to Shor's algorithm.
There are other quantum algorithms, but Shor's algorithm appears to be the main concern for cryptography.
The relevant mathematical problem appears to be "The Hidden Subgroup Problem":

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.
The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons:

Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the $\operatorname{poly}(n)$ unique SVP.

So post-quantum algorithms are built from problems that aren't equivalent to the Hidden Subgroup Problem for finite Abelian groups.
Symmetric Algorithms
For symmetric algorithms, the relevant threat is Grover's algorithm, which provides a speed up for the generic brute force search. Defending against this is simpler than defending against Shor's algorithm: Simply double the size of your keys and hashes, and everything should be ok.
This is why AES-256 (and 256-bit keys in general) are recommended for "long-term security" - a 128-bit key could be broken for 64 bits worth of cost once your adversary has a full scale quantum computer capable of running Grover's algorithm.


Can Zk-SNARKs verify the results of turing-complete computations?

Yes. Express $f$ as a (say, Boolean) circuit. If $f$ is poly-time it will have a number of gates that is polynomial in the input size. A universal circuit $U$ is a Boolean circuit that evaluates any circuit up to bounded size (see e.g. this eprint from 2017 by Günther, Kiss and Schneider). The input to $U$ will be bits representing the structure of the circuit of $f$. Since $U$ is just another Boolean circuit, it can also be represented as a QAP as in the Pinocchio paper, or whatever the zk-SNARK uses.


Consider a linear 8-bit s-box $S$:

$$
c=S\cdot p,
$$

where $c$ and $p$ are 8-bit vectors, and thus $S$ is an $8\times8$ matrix. This means we can pick 64 different s-boxes in our design. This already gives an intuition on one weakness: there are $8!$ permutations for 8 bits, but we limit our design to "just" 64 of them.

Now on to the fun stuff: differential cryptanalysis. Linear s-boxes have the nice property that for ciphertexts $c, c'$ and their respective plaintexts $p, p'$:

$$
c\oplus c' = S\cdot p \oplus S\cdot p' = S\cdot (p \oplus p'),
$$

which is a very much unwanted property of linear s-boxes. In usual symmetric cipher design, a non-linear s-box is the main element to counter this kind of differential cryptanalysis.

For what it's worth, the same can be said about affine s-boxes ($c=S\cdot p \oplus b$ for fixed $b$).

Now consider (simplified) AES, where the s-box is constructed as some form of inversion (technically a multiplicative inverse in the Rijndael finite field):

$$
c\oplus c' = p^{-1} \oplus p^{-1} \neq (p\oplus p')^{-1}
$$

Here, the $(\cdot)^{-1}$ operator is not distributive, hence, this simplified attack does not hold.

Linear cryptanalysis uses a linear approximation of the s-box. It tries to "model" the $(\cdot)^{-1}$ operator (or the s-box of the studied cipher) as a linear map $S$, such that usually (with high probability) bits from plaintext map on ciphertext bits using this linear model.

If such a model can be found with a high bias, we may be able to distinguish ciphertexts, or even derive (part of) the used key.

AES is designed to be highly non-linear, exactly to resist this kind of attack; the multiplicative inverse is said to be highly non-linear.


File format of an $2048$ bits RSA public key

You've mostly pieced it out.  This is a DER encoding the the public key, and consists of a sequence of two integers (the first being the modulus, and the second being the exponent).

Here is the breakdown of the encoding:

30

The value 30 is used to signify 'sequence'; this is a container that carries a list of DER-encoded objects.

82 01 0a

Whenever we have an object (including a sequence), we always encode the length of the object (that is, how many bytes are in the DER-encoding of the object, not counting the object type and the length field); here, the 82 signifies that the length itself is 2 bytes long, and that the total length is 0x010a = 266 bytes.

02

Now, we get to the first object in the sequence; the value 02 is used to signify 'integer'.

82 01 01

And this is the length of the integer; again, the 82 signifies that the length itself is 2 bytes long, and that the total length is 0x0101 = 257 bytes.

00 8e a3 d1 c7 ... ab 23 39 2d

These 257 bytes are the actual integer, in bigendian format.  Note that the first byte is a 00; that is required because of the rules of DER encoding.  Specifically, the 02 format encodes an integer, and it is allowed to encode a negative integer (remember, DER is a general format, and is not targetted specifically to encoding public keys).  The rule is that the integer is negative if the msbit of the encoded value is a 1.  We need to encode a positive integer; the top byte of the value we encode is 8e, which has a msbit of 1.  To prevent this from confusing the decoder, we prepend a 00 on top to make the msbit 0.

And, while you didn't ask about the end part, here are the last 5 bytes:

02

This signifies that the second element in the sequence encodes an integer

03

This signifies that this integer is encoded in 3 bytes

01 00 01

This signifies that the encoded integer is 0x10001 == 65537


If you can generate uniform random numbers, you can use a variant of Fisher-Yates.

//given an array s with the elements to be permuted
for i from n-1 to 1:
    t = rand(0, i) # inclusive
    swap(s[i], s[t])


Why is cryptographic model not considered formal methods?

Disclaimer: I'm currently doing a PhD in Formal Methods and Cryptography and I'm not really sure of my answer.

The first application of Formal Methods is to be applied to pieces of software. The goal is to prove security properties on them. These are usually safety critical softwares (those you find in planes, trains, nuclear facilities...) This field is called Software Verification.

I mostly consider Formal Method as a way of arguing, a way of thinking or proving. In this case, Formal means without ambiguity. Thus you could consider any approach with such mindset in the domain of Formal Methods.

To answer your question, [from my point of view,] both approaches qualify as in the Formal Methods (and I don't see why they should not).

E.g. Easycrypt, a tool to make proofs in game based model and probabilistic models is based on Why3. And I'm pretty sure that Why3 is part of the Formal Methods approach using theorems provers and SMT solvers such as Alt-Ergo or Z3.


Non-malleability of One Time Pad Encryption

The Problem

The One-Time Pad offers perfect secrecy. However, it does not protect the integrity or authenticity of the message - An adversary can flip bits of the ciphertext, and the receiver will have no way of detecting the manipulation.

Consider the case where a single bit is sent encrypted with a One-Time Pad, used to indicate a "yes/no" value as to whether or not Alice wants to have lunch with Bob. If Mallory intercepts the message $C$ and computes $C \oplus 1$ and then sends that value to Bob instead, Bob will receive the opposite of Alice's intended message - and he will have no way of knowing that it has been tampered with.

The solution

Use a MAC to ensure the integrity and authenticity of the message.


Why do I need to add the original salt to each hash iteration of a password?

Given that SHA-512 is used, there is no practical benefit to iterating hash = sha512(salt + hash) compared to iterating just hash = sha512(hash). For some parameters, it even weakens the scheme by a factor of nearly 2 against the attack that most matters: guessing the password.

Let's first justify the weakening. Assume salt is 125 bytes. salt + hash is 1512 bits long, and two SHA-512 rounds (each hashing 1024 bits) will be used by the legitimate user to compute hash = sha512(salt + hash), rather than one round for hash = sha512(hash). On the other hand, the adversary trying millions of passwords can pre-compute the result of one SHA-512 round for each of the $2^{24}$ 1024-bit strings starting in salt, then replace the first round of each computation of hash = sha512(salt + hash) by a table lookup in that 1 MiB table. The ill-advised idea of hashing salt prevents legitimate users from about doubling the number of iterations at constant effort/time, when it is only a marginal annoyance to attackers.

In theory, when using some unspecified hash function H, it is a reasonable idea to perform something like

var hash = H(salt + password);
for (i = 0; i < n; i++) {
    hash = H(hash + i + salt + password);
}

A rationale behind hashing i is that it makes it highly implausible that a short cycle could be reached in the iteration, regardless of considerations on the width of hash. Without this precaution, if hash is $b$-bit, odd of entering a cycle on or before $n$ iterations are about $n\cdot(n+1)/2^{b+1}$ (when $n\ll2^{b/2}$).

A rationale behind hashing salt or/and password or/and i is that it makes it impossible for an adversary to perform a precomputation that would be conceivable for iterated hash = H(hash) if the adversary can hope to ever perform next to $2^b$ hashes and store next to $2^b/n$ values. Assuming that, an attacker could pre-compute the result of $n/2$ iterations for values of hash less than $2^{b+1}/n$. During the normal computation for a given salt + password, there is good chance that such low values of hash is reached, and the precomputed table usable as a speedup. Edit: it seems quite likely that the number of hashes or/and the memory necessary can be greatly improved, perhaps even to $O(2^{b/2})$ hashes or $O(2^{b/2}/n)$ values, though I can't figure how for now.

The above two things could be an issue when $b=128$ (e.g. when using MD5); but are a complete non-issue when $b=512$ (our situation since SHA-512 is used).

A rationale behind putting hash first is that it avoids the pitfall we first studied, when H is an iterated hash function starting with the beginning of the message, as most practical hash functions are.

Update following comment: a rationale behind not iterating hash = H(hash + password) (but rather including salt and i in the mix), when the width $b$ of the hash is small, and the number of iterations $n$ high, could be that in the former case an adversary might get some advantage by a strategy where for each plausible password she performs some precomputation on common values of password giving it some sizable advantage in recognizing password from the final value of hash, especially if many pairs (salt, full final hash) are available.

As an example of such a strategy, assume that $b=64$ and $n=2^{30}$. For any given password, a sizable fraction of salt values are such that a cycle is entered during the legitimate computation, and a powerful adversary can tabulate, independently of salt, a sizable fraction of the lower values of hash reached in such cycles. Then, for each final value of hash at hand, and each password, the adversary can iterate perhaps $2^{26}$ times, test if any of the (smaller) values reached is in the precomputed table, and in the affirmative make a full test for this password. Odds of recognizing a (salt,password) pair for a given effort are improved compared to pure brute force (at least when the number of password tested is such that a few are among the (salt,password) pairs, and neglecting the cost of the precomputation and table lookups; and I guess, with some refined strategies, even accounting for these costs).

Again, using $b=512$ is plenty appropriate to make iterating hash = H(hash) entirely satisfactory (assuming an attack using classical computers). It even seems possible to make a formal reduction from any attack against that to an attack on the hash (to keep the proof simple, it might help to prevent salt + password from having the same size as hash, e.g. by using a 65-byte salt).

And notice that there is at least one excellent reason not to include password in the mix: making it less likely that password could leak by some side channel on a legitimate user's platform, perhaps by a mechanism remotely similar to this.

Final note: the state of the art is not iterating a hash, but rather iterating a function requiring a large (and preferably parameterizable) amount of memory, and as an aside such that the efficiency on the legitimate platforms using commodity multi-core CPUs is as good as possible, which makes dedicated hardware less attractive for the attacker; see scrypt, or bcrypt (still more common although it lacks parameterizable memory size, use of multiple cores, and seems less close to optimality on commodity CPUs).


How to use ECDH keypairs algorithm for encryption and decryption same like RSA keypairs without key agreement?

Yes. You can for instance use ECIES. As there is no encryption counterpart for ECDSA (for digital signatures) it is however based on ECDH (Diffie-Hellman key agreement). This also means that it is required to send a public key together with the ciphertext.

Basically ECIES performs key agreement in an offline fashion and then encrypts the message with the resulting secret key. This in turn means that a symmetric cipher (stream cipher, authenticated cipher or just a block cipher + mode of operation) is required. It could also mean additional overhead as the public key of the encrypting party needs to be send with the ciphertext.

Using an asymmetric primitive together with a symmetric primitive such as a block cipher or hash is called a hybrid cryptosystem.

Notes:

The sender and receiver need to configure / accept a common set of domain parameters - this are commonly parameters of a named curve.
There is also a DH counterpart called IES, ECDH is based on DH and ECIES is based on IES.
By default many implementations do not offer integrity or authenticity protection and may - in the worst case - be susceptible to plaintext / padding oracle attacks. You may want to use a signature and/or authenticated encryption instead of e.g. ECB or CBC mode encryption.
ElGamal encryption may also be used (as SEJPM notes in his comment) although this may leave you with specifying more of the underlying protocol.


You have a typo, $x$ is also in $\mathbb{F}_2^4,$ since the Present Sbox is $4\times 4$ bits.

The quantities $S(x),a,b,x$ all lie in $\mathbb{F}_2^4,$ and the inner products such as $\langle b,S(x)\rangle$ etc lie in $\mathbb{F}_2.$ We now treat the inner product values as in $\mathbb{N},$ so we can calculate
$(-1)^{\langle b,S(x)\rangle+\langle a,x\rangle}.$

Basically if the two inner products in the exponent match we have a $+1$ in the overall sum, otherwise a $-1$. Thus the sum computes the imbalance function defined as $$2^4-2d_H(\langle b,S(x)\rangle,\langle a,x\rangle)$$
between the two quantities in the exponent as $x$ ranges over $\mathbb{F}_2^4.$

Here $d_H$ is the hamming distance along the truth tables.


In the "ideal cipher" model, the block cipher is a permutation of the space of input blocks, chosen uniformly among all such permutations. A plaintext that gets encrypted to itself is a fixed point for the permutation; it is expected that about 63.21% of all permutations have at least one fixed point (a permutation with no fixed point is called a derangement).
Thus, assuming that AES is an ideal cipher, then it is expected that for about two thirds of possible keys, there will be at least one plaintext block that is encrypted to itself.
Now, finding that fixed point is quite another thing; we in fact expect not to be able to easily find that fixed point or even ascertain whether it exists or not -- the "moral" reason is that finding a fixed point on a random permutation requires hitting it exactly, which is akin to a brute force on the whole input space, of size 2128 in the case of AES. In other words, if we could find fixed points or even prove (non-constructively) their existence or non-existence for any specific key, then this would mean that we could differentiate AES from the ideal cipher model, and that would be worrying.
(See also that answer on crypto.SE.)
Note: while a majority of AES keys should have at least one fixed point, it is strongly expected that there is no key that turns AES into an identity function (i.e. all plaintexts being fixed points): there are 2128! ≈ 22135 possible permutations, a number waaaay larger than the 2256+2192+2128 possible AES keys, thus the identity permutation is very unlikely to correspond to a key. But then again, we don't expect to be able to prove it.


Finding a solution to a (sort of) discrete logarithm by asking questions

I'll give a sketch of the solution to a quite similar problem (that makes more sense to me). The purpose of this modified problem is to show that it is essential to take $g$ of order exactly $q$ in the given setup, as one otherwise gets an oracle returning $u^x$ given $u$ as in your problem. (I'll show the connection between both problems (yours and mine) at the end of my answer.)

  Let $p = kq + 1$ and $q$ be primes such that $\log{q} \approx n$, $\log{k} \approx n$ and such that the bit size of every prime factor of $k$ is bounded
  by $\log{n}$. Let $g$ be an element of $Z^*_p$ of order $k'q = p-1$, where $k'\mid k$.

  $x \in$ $Z_q$ is picked randomly and you get $g$ and $y = g^x$.

  How would you go ahead to compute $x$ efficiently?

1) Write $k = \prod_i r_i$ as product of (pairwise coprime) prime powers r_i.

As $k$ has only small prime factors, you can find this factorization.

2) Define $g_i := g^\frac{kq}{r_i} = g^\frac{p-1}{r_i}$, and find its order $s_i$ in $Z^*_p$, which has to be a divisor of $r_i$.

3) Set $y_i := y^\frac{kq}{r_i} = y^\frac{p-1}{r_i} \in \langle g_i\rangle$ and determine $x_i \in \{0, 1, \dots, s_i-1\}$ with $g_i^{x_i} = y_i$.

As $s_i$ is the power of a small prime $p_i$, you can find $x_i$ by finding first $x_i \bmod p_i$, then $x_i \bmod p_i^2, \dots$ (please tell me, if you need a further hint for this).

4) Convince yourself that $x_i = x \bmod s_i$ for all $i$, and use the Chinese remainder theorem to find $x'$ with $x' = x \bmod \prod_i s_i$ (by definition $k'=\prod_i s_i$). As $x < q$ (we chose $x \in Z^*_p$), there are not many candidates $x' + l\cdot k'$ for $x$ as long as $\log k' \approx \log q$ (if $k' > q$ one has $x = x'$).

You can get from your problem to mine by finding a generator $u$ of $Z^*_p$ (you are able to find this generators as you know/can find the factorization of $p-1$), and applying once your oracle to obtain $u^x$ (with the nice extra property $k=k'$). I use then the relation between $g$ and $y$ to get a special oracle: $g_i$ corresponds to $u$, and $y_i$ to $u^x$.

Final remark: Instead of picking the random $x$ in $\{0, \dots, q-1\}$ one can could pick $x \in \{0, \dots, p-2\}$ to prevent anyone from finding $x \bmod q$, but giving away unnecessarily information about one's random source doesn't feel good and wastes resources...


This smells like a HW question, so the OP should try it with more hints.

By querying this function at $x$, it is easy to tell whether $x\geq n$ or $x<n$. Let $k$ be a natural number such that $2^k<n\leq 2^{k+1}$, how many queries do you need to find this $k$? Knowing this $k$, how can you figure out $n$?

If the modulo operation is part of polynomial division with remainder, you could find the degree of $n$ using binary search. Once you know the degree, you can query another polynomial to find $n$.


Is there a signature scheme which doesn't rely on the difficulty of factoring/dlp which generates short signatures?

There are actually quite a few of these. Interest has been raised on this topic mainly due to the "post-quantum" security of such schemes. Also, Lamport is only a one-time signature, and we want a full-blown signature schemes.

For just one example see, SPHINCS: https://sphincs.cr.yp.to/sphincs-20150202.pdf.


How to encrypt a 192 bit plaintext using AES-192?

Strange as it may sound, you should not directly use any block cipher directly as a means to provide confidentiality. A block cipher can only handle a statically sized plaintext, which in the case of AES is always 128 bits; it's not 192 bits, that's just the key size.

More importantly a block cipher will always output the same ciphertext if the key and input block remain the same. That means that if you input two 128 bit messages, for instance the ASCII representation of "affirmative, sir", then the ciphertext will be identical. If this message is the answer of two separate questions then an adversary can immediately detect that the answer of two questions is identical as well. This breaks the security of a cipher as it leaks information about the plaintext.

In the strongest semantic security that a cipher can obtain, IND_CPA, the ciphertext output should not leak any information even if the adversary may input as many input messages as he likes.

The simplest mode of operation is ECB mode; it just splits the plaintext into multiple blocks, and then encrypts each block in turn, possibly padding the last block so that the input to the block cipher always receives 128 bits. This solves the first part of the cipher only handling 128 bits, but it does nothing for the security mentioned in the previous sections.

Fortunately there are many modes of operation that do provide such security. AES-CBC is used a lot, but it requires padding - which in itself can be a security risk - as well as a unpredictable IV. This IV or initialization vector is used to change the ciphertext independently of the plaintext. AES-CTR (AES in counter mode) is also used a lot and doesn't require the padding and only a unique nonce (number-used-once) instead of the unpredictable IV.

Currently authenticating ciphers such as GCM are becoming more commonplace as they do not just protect the confidentiality but also the authenticity and integrity of the message. They are generally build using AES-CTR internally.

Note that the size of the plaintext is not automatically protected by AES using any of the modes of operation. This is one of many side channels that may leak information to the attacker. You cannot just encrypt "Yes" to 3 bytes ciphertext and expect that an adversary cannot distinguish it from the 2 bytes required for "No".

When you read about AES-192 is being used to protect your data then you should ask yourself how it is used to do this. To a seasoned cryptographer the use of AES, as the most common unbroken block cipher, only means that a small part of a system is possibly secure.

If you want to encrypt fully random data (such as an AES key) then you could right-pad your data using 64 bits set to zero. Then you could use ECB mode encryption (encrypt two blocks of 64 bits) and encrypt the two blocks of 128 bits. This process is called key wrapping. This is only secure for completely random data though and it is probably better to use more modern techniques such as AES in SIV mode.


CBC mode encryption is defined as:

$C_i = E_k(P_i\oplus C_{i-1})$

(with $P_i$ being the $i$th plaintext block, and $C_{i-1}, C_i$ being the ciphertext blocks.

What might happen if we have a lot of ciphertext encrypted with the same key is if two ciphertexts happen to be the same, that is:

$C_i = C_j$

If we see that, we can then immediately deduce that:

$E_k(P_i \oplus C_{i-1}) = E_k(P_j \oplus C_{j-1})$

or

$P_i \oplus P_j = C_{i-1} \oplus C_{j-1}$

Now, the attacker knows the values of $C_{i-1}, C_{j-1}$, and hence the attacker can then deduce the relationship between those two plaintext blocks.  If he happens to know one of the plaintext blocks, he can immediately deduce the other.

Is this information leakage fatal?  Well, maybe, maybe not, the attacker has no control over what data blocks are leaked, even with chosen plaintext (because he can't predict $C_{i-1}$ before the encryption process).  However it's more leakage than we want.

And, how likely is this?  Well, that's where we come to block size.  $C_{i-1}$ is effectively random and uncorrelated to $P_i$, and so $P_i \oplus C_{i-1}$ is also effectively random; if the block size is $n$ bits, this is a random value between $0$ and $2^{n}-1$; by the birthday paradox, we would expect a collision after about $2^{n/2}$ block encryptions.

That is the point in not using too small of a block size; if we were to take $n=32$ bits, we would expect a collision (and hence some leakage) after about $2^{16}$ blocks; since we generally want to encrypt more than that with a single key, that's not enough.  For $n=64$, we would expect a collision after about $2^{32}$ blocks; that's getting better, however by today's standards, that's not that much data (and there is a chance of leakage with less data).  For $n=128$, we probably won't get a leakage until we get close to $2^{64}$ blocks; we'll never encrypt that much with a single key.


How to express difficulty of breaking crypto when writing?

Your technical readers will gloss over the example. If you use this try to use fixed pitch for the large numbers.
The technical term is computationally infeasible. But as an example consider the two numbers:
 7,500,000,000,000,000,000
18,446,000,000,000,000,000

The first is 7.5x1018, the second number is somewhat less than 264.
The first number is a reasonable guess of the number of grains on sand on planet earth. The second is the number of different 64-bit numbers. Trying to check each one would take many very fast computers a very long time. But today, doing so is Giga-flippin’n hard but is still possible given a large budget. Please note that adding a single bit doubles the number of possible values.
The minimum key size for AES is 128 bits. That’s 3.4x1038 possible short keys.
There is some concern that quantum computers may someday be able to break AES if only minimum key sizes are used. AES is often used with 256-bit keys.


Symmetric mutual authentication with client using a derived secret

The general answer is "no, you can't authenticate someone over a wire unless they know some secret information." The only way to authenticate someone is to have them do something that no one else can do. If you're trying to do it by just sending messages between the parties, the only way I can do something that someone else can't is if I know something they don't (whatever I would send is based only on things I know; if they know what I know they could figure out what I would send themselves).

Your scheme isn't quite that, though. You do have a secret on each side; in fact, it's the same secret on each side (i.e. CT). With a shared secret, authentication absolutely becomes possible; when the shared secret is high-entropy (i.e. not derived from a password), it's even better. MACs should be a decent way to achieve this, although I'd be wary of possible pitfalls (one notable one being that an attacker could get whatever he wants MACed by the server, but with a strong MAC this only allows straight replay, and the scheme stops that).

The other part of your scheme is deriving the shared secrets from a server master secret. If the idea of using HMAC with a secret key to derive client tokens is that you don't need to have a master list of client tokens, then that seems like a sensible approach; HMAC should stop an attacker from creating any secret tokens that they don't already know from other sources. TLS uses HMAC as a PRF to produce cryptographic keys from a secret, so it's a perfectly reasonable choice (the way TLS uses it is having a seed and computing HMAC(secret, label+seed), but in your case you don't need a label).

Much depends on what you plan to do after authentication -- if they'll keep communicating, nothing you did prevents an attacker from tampering with the rest of the communication. For instance, an attacker can hold up message 3 and then send it days later. Is this a problem for your protocol? If so, you have to deal with it somehow.


Is there a point in storing hash or plaintext in the last column of Rainbow Tables

The Rainbow table's average chain length determined during design time. Let cal it $t$.

If we want the table contains $N$ entries we need at least $N/t$ endpoints. To save storage, you want to make $t$ big as much as possible, but up to some point. $t$ determines the search time, $t^2$. You may want to reduce the space if you have a change, that can speed up the table lookup timing.

The storage table is a pair;

| Start Point | End Point |

In password cracking

if you store the hashes as the endpoints then we can immediately search on the endpoints for the given password hash.
if we store after the reduction, as in Wikipedia or Oechslin we need to first apply a reduction to the given hash value, then we can search.

If you are looking for 128-bit size passwords and building the table for SHA256, then for the endpoints, instead of storing the hash you can store the reduced value. In this case, you will gain approximately $\frac{128 N}{t} $ bits with a cost of applying a reduction for every new search. Therefore, if there is a space gain is available it is preferable.

Interestingly, most passwords are weak, instead of building the costly Rainbow table, a hash table that contains only the weak passwords is a better alternative.


Why can we always assume that $Gen$ algorithm choose key uniformly?

Are you trying to prove this for a specific encryption scheme or for any scheme?

If you have a specific scheme in mind, you can consider using rejection sampling.
In your case, it would be quite straightforward to use :

Let's say each key $k\in \{0,1\}^n$ is output by $Gen$ with a probability $p(k)$, and $p_{min} \overset{def}{=} \min\limits_{k} p(k)$.
You can then define $GenU(1^n)$ per example like this :

$GenU(1^n):$

1) $k \leftarrow Gen(1^n)$

2) With probability $p_{min}/p(k)$, output $k$, otherwise restart

You can see that an iteration of $GenU$ outputs each $k$ with probability $p_{min}$, and terminates ($ie$ does not restart) with probability $\sum_{k} p_{min} = 2^n\cdot p_{min}$.

Now, this algorithm assumes that you can efficiently compute each $p(k)$. Moreover, if $p_{min}$ is much smaller than the other values of $p(k)$, then $GenU$ may take an impractical amount of time to terminate ($eg$ if $p_{min} = 2^{-2n}$, then an iteration $GenU$ will terminate with probability $2^{-n}$).

For these reasons, if you want to prove your proposition in the general case, you cannot apply this algorithm as it is. Hope it helps though.


Cracking simple RSA when just the ciphertext and one public key is known

Running RSA backwards would imply cracking the key (determining the private key) and you could brute force that by factoring.  You could generate all possible prime's of the requisite size until you could generate the known public key.  Or perhaps there are other approaches that are more mathematical, that could factor for the primes, which would also be a form of brute force, as currently factoring is thought to be a NP-hard problem.


Is the encryption more secure if we apply Pohlig-Hellman cipher twice with different keys but with the same modulus?

So is this more secure than doing it just once or not.

TL;DR; No, multiple encryptions are equal to single encryption and this is not better than single encryption

Pohlig-Hellman Cipher

In setting up of Pohlig-Hellman Cipher;

Select a large prime modulus, let say $p$,
then select a public modulus $e$ with $\gcd(e,\varphi(p))=1$ otherwise no unique decryption.
so, we have a public key as $(e,p)$.
Your private key is the tuple $(d,p)$ such that $e \cdot d \equiv 1 \bmod \varphi(p)$.

To encrypt a message Alice take a message $m < p$, then encrypt you with $$c = m^e \pmod p$$

Once, you get the message you decrypt by $$ c^d = m^{e\cdot d} \equiv m \pmod p$$ with the help of the Little Fermat Theorem.

Example:

p = 3001
e = 37
d = 973

let $m = 57$ then $c = 57^{37} \equiv  2778 \pmod{3001}$

with $c = 2778$ then $ m = 2778^{973} = 57 \pmod{3001} $

Cascade Property: Double encryption is single encryption

To show the cascade property we will use the same modulus with different parameters. This will show that double encryption is equal to single encryption.

Let $p$ is the modulus, $(e_1,p)$ and $(d_1,p)$ be corresponding pairs and $(e_2,p)$ and $(d_2,p)$ be another pair. Let encrypt a message $m$ with the first public key then with the second.

$$c_1 = m^{e_1} \pmod p$$ then
  $$c_2 = c_1^{e_2} = (m^{e_1})^{e_2} = m^{e_1 \cdot e_2} \bmod p$$

Let call $e' = e_1 \cdot e_2 \pmod{\varphi(p)}$ and $d = e'^{-1} \pmod{\varphi(p)}$

Therefore $(e',d')$ will be the single key for the double encryption

Example:

Continue the previous example with $(31,3001)$ and $(871,3001)$ as second public and private keys.

$$2778^{31} \equiv 197 \pmod{3001}$$

$$e' = 31*37 \equiv 1147 \pmod{3000}$$

$$d' = 1483 \pmod{3000}$$

Now, decrypt with $d'$

$$ 197^{1483} \equiv 57 \pmod{3001}$$

Some notes on Pohlig-Hellman Cipher

It is vulnerable to KPA.
It is not IND-CPA secure
It is Multiplicative
No probabilistic Encryption.
Security relies on the discrete logarithm
The prime $p$ must be chosen properly, safe prime*, against Pohlig-Hellmans' algorithm for finding a discrete log.

*A safe prime is a prime number of the form 2p + 1, where p is also a prime


Checking the share membership in secret sharing schemes

Just to be specific we are talking about information theoretically secure secret sharing, e.g. Shamir sharing. Lets say a secret $secret$ is shared in $n$ shares $S = \{s_1, \ldots, s_n\}$. Assume further party $P_i$ is given share $s_i$. If I understand your question correctly, you are asking if we give $P_i$ some share $r \ne s_i$ is there anyway for $P_i$ to decide if $r \in S$?

If that is the question, I think the answer is, "no", since it would contradict the properties of secret sharing.

Here is my argument: Assume we give $P_i$ some help. We give her $t - 2$ shares from $S\backslash \{s_i, r\}$. Now $P_i$ has $t - 1$ shares of $secret$. Now $P_i$ can take $r$ and in total have $t$ shares (possibly with one share not being correct). This is enough to reconstruct some secret $secret'$. If and only if $r \in S$ we have "secret' = secret". So if $P_i$ could tell if $r \in S$, then $P_i$ would know whether or not $secret' = secret$. However, this contradict the property of secret sharing that $t - 1$ shares gives no information on the secret.

In fact since this is information theoretic security even a brute force attack will make no difference.


What does variable-base point/scalar multiplication mean in ECC?

Yes, you are correct. There are various methods for scalar multiplication on elliptic curves.

Some of them are optimised for fixed base-point scalar multiplication, i.e., where you a-priori know that you will mostly/exclusively perform scalar multiplications with respect to a fixed base point on the curve. Thus, one can make (extensive) pre-computations (e.g., as done with the the fixed-base Comb multiplier). Think for instance of a scenario where you extensively issue ECDSA signatures, then you always do your scalar multiplication using to the same fixed base point.

Other methods are not optimised to some a-priori fixed point and thus are useful for variable base point scalar multiplication, which often arises in other cryptographic protocols where you do not know the point you will be using a-priori.

Clearly, there are many criteria to decide which multiplier you will use such as speed, side-channel resistance or memory footprint.


Why discrete logarithm modulo composite moduli not popular and not defined in standards?

Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards?

Actually, it would not be an "additional barrier", instead, it would be an additional avenue of attack.  After all, the standard attacks against a discrete log problem still work in a composite modulii; in addition, the attacker has the possibility of factoring the modulii, and then solving the discrete log problem modulo each prime factor.  The primes are considerably smaller than the full modulii, and hence those subproblems are comparatively easy to solve; the difficulty is dominated by the factorization effort.
You state in your rephrasing "what if we had an Oracle that solved the discrete log problem modulo a prime (but not a composite)", well, since we have no indication that such an Oracle exists, we don't worry too much about it.
In any case, your construction to change that to "what if we had an Oracle that solved the factorization problem" (because once we've factored, solving the discrete log modulo the smaller prime factors is comparatively easy).
On the other hand, that really doesn't answer the question "why don't standards do that?"  Well, I didn't write the standards, so I can't give an authoritative answer there; however I would note that it makes it considerably harder to come up with a Nothing-Up-My-Sleeve group; that is, a group that we are pretty sure is actually secure, and that no one has a backdoor to.
For prime modulii, it is fairly easy to design a deterministic process that, at the end, generates a "good" prime number; that is, one where we know the large prime subgroup, (and which is not vulnerable to the Special Number Field Sieve algorithm); with that, we are fairly confident that it was not designed with a special vulnerability in mind.
In contrast, we don't have such a good way to have a deterministic process that generates a composite number of unknown factorization (and which is known to be hard to factor), and also has a large rough [1] subgroup with a known generator.  What we are likely to do is rely on some trusted authority to generate one for us.
Well, the "trusted" part is a deal-breaker for quite a few; there isn't anyone which everyone would agree should be trusted with coming up with our crypto parameters.  And, yes, "trust" is the right word; there are a number of ways a dealer can generate a composite modulus for which they can solve the discrete log problem, but other people can't (essentially by using different prime factors for which they can solve the discrete log problem, and then multiplying them together to hide things).
[1]: By rough, I mean one with no small prime factors.  This is not standard terminology (hence this footnote); this is the obvious antonym to "smooth" (consists only of small factors).


Optimal MDS matrix - circulant or recursive?

my answer is extension to circulant and recursive.

one property measure to the optimal implementation of MDS matrix in cryptography is the cost of xor (number of xors required to fully implement the MDS matrix ) , depth (number of stages) and the field size (usually 4 or 8 )

according to this paper MDS Matrices with Lightweight Circuits, the native implementation of AES MDS matrix costs 152 xors , with the improved algorithm is reduced to 97 xors and depth of three stages.
they searched for others MDS with different structures such as Toeplitz and Hadamard.

Figures below show better MDS matrices in term of implementation compared to circulant AES MDS .

In addition to hardware cost, the security aspect of MDS matrix has appeared in this paper : MixColumns Properties and Attacks on (round-reduced) AES with a Single Secret S-Box, which takes advantage of MDS values.

At the end , it is your call which MDS matrix to be implemented , you need to look it from security and hardware implementation cost.


the key and plaintext is the same. The attacker knows this and the IVs used but doesn't know the plaintext. Is there anything to learn about the plaintext when multiple ciphertexts are available instead of only one?

No. Giving the attacker multiple encryptions of a single plaintext using a randomly chosen IV and a fixed key with AES-CBC does not leak any more information about the plaintext than does a single ciphertext.

In fact if the attacker didn't know whether or not they were the same plaintext (but had the same length), the attacker couldn't tell you whether or not they encrypted the same plaintext.


Practical consequences of using functional encryption for software obfuscation

Are the results as ground breaking as the article suggests?

This result will prove to be a very important one for theoretical crypto. The analogy to fully homomorphic encryption (mentioned above by Samuel) is useful, since that is another well-known result that was hugely groundbreaking from a theoretical point of view, but even years later the constructions are not what one would consider "practical."

  does anyone have a clear idea regarding exactly what aspect of an implementation the method will potentially obfuscate?

The obfuscated program will hide all aspects of the implementation, except for the output. That's the definition of obfuscation. Well, mostly. The most natural definition of obfuscation is impossible to achieve in general. Without getting into too many technical details, this paper shows how to get something weaker called "indistinguishability obfuscation", which is known to be the best possible kind of obfuscation you could hope for in light of the impossibility result. Unfortunately, it's somewhat difficult to interpret exactly what you get from indistinguishability obfuscation. The authors do mention this in their paper.

  Does it only apply to hardware implementations at the integrated circuit level?

There's nothing really specific to hardware in this paper. You can obfuscate any program, hardware or software. But perhaps the confusion comes from the fact that, in order to user their obfuscation, you have to express your program as a boolean circuit (of AND, OR, NOT gates), not as a Turing machine or assembly code or C or whatever. This is pretty standard in the theoretical literature, but a source of a lot of the impracticality of these kinds of constructions.

  Does it apply even if the adversary is able to track and map signals once the chip is turned on? Does it apply to software implementations for generic platforms, even if the adversary has full control over the CPU and internal memory (e.g. in case of emulators)?

There are no such restrictions on the adversary. Thinking at the software level, the obfuscated program is just a big blob of 1s and 0s that you hand over to the adversary. Now the adversary can do whatever it likes with the blob of data. The security guarantee (more or less) is that the only useful information that the adversary can get out of this blob of data is the ability to execute the program on inputs of its choice. Sure, this covers situations where you imagine the adversary to have full control of the hardware on which the obfuscated program is executing.


Using simple hashing function to expand already secure key

What you are looking for is a "Key Derivation Function" (KDF).  Notice you called out PBKDF - Password Based KDF.   One very common KDF (it's even in NIST standards) is to use the shared secret - your "master_key" - to hmac a counter.  Your proposal is therefore in line with the standard methods of KDF.


What kind of symmetric-key algorithm to use with Diffie-Hellman?

What you are looking for is a key-derivation function.

As you have correctly observed one can make mistakes when using a shared secret and the KDF does exactly what you want.

A typical implementation would be a hash.

Note that short keys are not really an issue here. They should only occur with appropriately small probability and when padded with zeros would be acceptable keys.


How the coin flipping protocol prevent Alice from generating $ n $ from many primes?

Note that Step II of the protocol is titled "ALICE TESTS n" and this includes a method for Alice to verify that Bob chose n correctly. This appears on the third page of the paper.


What are some good references for the implementation weaknesses in RSA

It depends on what you are using RSA for and how deep of an understanding you would like.

A sort of general overview of RSA and potential attacks against textbook RSA is presented in the Handbook of Applied Cryptography, specifically chapter 8. (Note that the entire text is free online.) Chapters 11 and 12 also are useful to read, as they focus on specific instances of RSA. This will give you a good, brief understanding of the generics of RSA, but I wouldn't go implementing the algorithm straight out of the HAC.

Instead, if you'd like to know a good standard for implementing RSA in specific instances, I'd recommend one of the many standards on the subject (PKCS, FIPS, ISO, ...). On Wikipedia, you can find this List of PKCS. You might be interested in PKCS#1. Note that the actual RSA Labs maintains a PKCS list of its own, where you can find PDFs of the various PKCS (usually: that or .ps files). I find PDFs infinitely more pleasing to read than RFCs, so that might pique your interest.

Further, the NIST maintains a Current FIPS list. So, for example, if you were interested in using RSA for signatures, you might look at FIPS 186-3.

PKCS and FIPS aren't big on theory, however, so if you are looking for a good theoretical understanding, the HAC is probably your best bet. You might also want to look up actual published attacks in the literature. For example, searching rsa padding returns many useful results, e.g. Why textbook ElGamal and RSA are insecure by Boneh, Joux, and Nguyen. That isn't so much a reference for secure implementation, but it certainly highlights the possible attacks on the textbook implementation.

Also, you probably want to look at other known-good implementations like GPG and OpenSSL.


Is it okay to include relative time for true random number generation?

Who can tell when my machine was booted?

Anyone who observed it go on, at least. That could include someone sniffing your wlan traffic. However, if the computer in question is a shared server, anyone with access can probably call uptime.

  After all, /dev/random uses timings for it's cryptographically secure output.

In setups where timing information is included (in a way that counts entropy), the thing being timed is supposed to be unknowable. For example, the least significant bits of when a physically present user presses a key.

In theory, even that isn't necessarily unknown (e.g. wireless keyboard), but since there is additional variation in how long it takes until the kernel knows about it and the entropy estimate is quite pessimistic, it is assumed to be.

However, in my opinion the most important thing to keep in mind is that you only need the TRNG to produce something like 256 bits on output. Use that to seed a CSPRNG and you can produce more output than you could ever use.

So if you have a truly random process, measuring the non-time values should be enough to quickly collect the required amount of entropy. You can throw time values into the entropy extractor if you like, but you don't need to credit them with entropy if you get enough anyway.


Get $a$ such that quadratic residue has a solution (Rabin)

The equation $a = x^2 \bmod N$ has at most $4$ solutions $x$.

There are solutions if $a$ is a square modulo both $p$ and $q$.  This can be checked by computing the Legendre of symbol of $x$ modulo $p$ and modulo $q$.

Assuming that the two Legendre symbols are +1, when $p \equiv 3 \pmod 4$, a square-root of $a$ modulo $p$ is given by $x_p = a^{(p+1)/4} \bmod p$; the other square-root modulo $p$ is given by $-x_p$; and simililarly modulo $q$.  The square-roots modulo $N$ are then obtained through Chinese remaindering (CRT): $x_1 = \mathrm{CRT}(x_p,x_q)$, $x_2 = \mathrm{CRT}(-x_p,x_q)$, $x_3 = \mathrm{CRT}(x_p,-x_q)$, $x_4 = \mathrm{CRT}(-x_p,-x_q)$.

For example, suppose $p = 852151$ and $q = 376963$ (note that $p,q \equiv 3 \pmod 4$).  And so $N = pq = 321229397413$.  Let also $a = 187078154864$.  It is verified that the Legendre symbol of $a$ modulo $p$ is $+1$, and similarly modulo $q$.

From the previous formula, we obtain $x_p = 295070$ and $x_q = 21456$.  The four square roots of $a$ are then obtained through Chinese remaindering: $184209776740$, $156318284370$, $164911113043$, and $137019620673$.

Remark 1:  The Legendre symbol of $a$ modulo $p$ is given by $a^{(p-1)/2} \bmod p$.

Remark 2:  Given $x_p$ and $x_q$, $\mathrm{CRT}(x_p,x_q) = x_p + p[i_p(x_q - x_p)\bmod q]$ with $i_p = p^{q-2} \bmod q$.


There are a lot of fancy things one can do when we start talking about sharing access a key store that Maarten mentions in this comment. I'll stick with just a very simple setup. You have a private key file (e.g., ssh private key). You don't want that file accessible to an attacker who steals your laptop, so the software asks you to supply a password to control access to that file.

The way these typically work is that symmetric keys are generated using your password (e.g., using bcrypt or PFKDF2). The keys are then used to encrypt the private key file. This would be done using an authenticated encryption mode of operation. These modes produce the ciphertext and a tag, which can be used to ensure that the ciphertext has not changed (note: a MAC like HMAC over the ciphertext would also work).

Now, when you supply a password again in the future to decrypt the file, the software runs that password through the same function to generate a key. If the same password is supplied, the same key is generated. Then it can attempt to decrypt the file. If the wrong key is supplied, or the ciphertext has been altered, decryption will fail due to the mode of operation used.

So it is the authentication tag over the ciphertext that is used to determine if either the wrong password was supplied or the ciphertext was altered.