Difference between Rijndael 128 / 256 blocksize implementations? (and impact of block size in general)

I'm just curious to know why the 128-bit version become the standard[.]

That question is easy to respond. In the section Minimum Acceptability Requirements of Request for Candidate Algorithm Nominations for the AES, it says:

  The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits. A submitted algorithm may support other key-block sizes and combinations, and such features will be taken into consideration during analysis and evaluation.

So, while supporting different block sizes is considered a desirable property, AES's block size was already decided before the competition even started, i.e., it has nothing to do with the Rijndael algorithm itself.

  I'm vaguely aware that a larger block size can help to mitigate some kinds of attacks... is that true? Which ones?

For some attacks, yes.

Some block modes of operation (e.g., CBC) require that the same ciphertext will never get generated twice. If $$E(C_1 \oplus P_1) = E(C_2 \oplus P_2)$$ ($P_i$ denotes a plaintext block, $C_i$ the previous ciphertext and $E$ the encryption function), since $E$ is bijective, $$C_1 \oplus P_1 = C_2 \oplus P_2,$$ and, therefore, $$P_2 = (C_1 \oplus C_2) \oplus P_1.$$

Since $(C_1 \oplus C_2)$ is known by design, if you know $P_1$ as well, you can derive $P_2$ (see: code book attack).

With a block size of $n$ bits, collisions become likely after roughly $2^\frac n2$ blocks of plaintext (see: birthday problem). This was a problem of DES (with a block size of 64 bits, $2^{32}$ blocks are only 32 GiB of plaintext). A block size of 128 bits ($2^{64}$ blocks are 256 EiB of plaintext) should be enough for the foreseeable future.

The same concern applies to other block modes of operation (e.g., CTR) as well, although it is not as easy to launch a successful attack. After roughly $2^\frac n2$ blocks, collisions should start to occur. However in CTR mode, $E(nonce+counter)$ won't produce any collisions in the first $2^n$ blocks. Therefore, the stream will become distinguishable from a random stream at a given point (see distinguishing attack).

  Could a larger block size also introduce weaknesses?

In general, yes.

Despite its simplicity, the cipher XTEA remains unbroken. However, its extension Block TEA (XTEA is Block TEA with a block size of 64 bits), is vulnerable to differential cryptanalysis (see: A Cryptanalysis of the Tiny Encryption Algorithm).

  I'm just curious [...] whether there's any good reason to use the 256-bit version.

Categorically no!

In AES proposal: Rijndael, the authors say:

  For Rijndael versions with a higher block length, the number of rounds is raised by one for
  every additional 32 bits in the block length, for the following reasons:

  For a block length above 128 bits, it takes 3 rounds to realise[sic] full diffusion, i.e., the diffusion power of a round, relative to the block length, diminishes with the block length.
  The larger block length causes the range of possible patterns that can be applied at the input/output of a sequence of rounds to increase. This added flexibility may allow to extend attacks by one or more rounds.

Furthermore, the authors recommend a number of round ($Nr$) of $$Nr = max(Nk, Nb) + 6,$$ where $Nk$ is the key size and $Nb$ the block size (both in 32-bit blocks).

This means that Rijndael-128-256 will be slower than Rijndael-128-128 (AES-128), and that Rijndael-256-256 may have a lower security margin that Rijndael-256-128.

Bottom line

Rijndael N-256 hasn't received nearly as much attention as AES, so it might have some undiscovered weaknesses.

In contrast, AES is considered secure, despite being subject to probably more cryptanalysis than any other cipher.

The 128-bit block size isn't a problem. If it ain't broken, don't fix it!


It is easier to generate a point with order $n$ than to find out the order of a random point:

Generate a random point $G'$ (generate random $x$ and solve for $y$)
Compute $G = hG'$ (multiply by cofactor)

This is guaranteed to generate a point $G$ with order either $n$ or $1$ (the point at infinity). The chance of generating the point at infinity is negligible, but you can check for it and regenerate $G$ if you want.

This procedure is described in section 3.1.3.2 "Point Selection" in SEC1v2, where it computes a generator from a seed $S$. It is more convoluted since it generates points verifiably at random.


If you are doing things right, then you will get the level of randomness you are after. Translation: you are not doing things right. You use AES with CFB8 mode, which requires a random initial value. The initial value is a 16-byte string which should be generated randomly and uniformly, and a new IV shall be generated for every single encrypted message. Since you need it for decryption, the IV for an encrypted message shall be stored/transmitted along with the said message.

Failure to use a new IV for each message results in a wide range of weaknesses, including what you are witnessing right now (if two strings begin with the same characters, the resulting encrypted strings will also begin with the same bytes).


Any weakness when performing SHA-256 repeatedly?

Answer

No, that would not be possible. It would be very weird indeed if a hash was suddenly invertible if the input was of a specific form - it would basically mean that the hash would be broken. Iterating over all the possible values of those 32 bytes is certainly not an option either.

Peculiarities

That does not mean that such a structure doesn't have it's peculiarities though, the first link provided by mikazo is a good summary of what to expect.

If you want to avoid such peculiarities then I would suggest you follow the suggestion by CodesInChaos to use a HMAC construct with a fixed key instead of SHA-256 directly. As e.g. length extension attacks not feasible with SHA-3 (Keccak) you can probably use that without reverting to a HMAC.

Notes

The inner state of SHA-2 is basically the output (after padding & inclusion of the message size); so a 32 byte input is certainly not an issue in itself, as the inner state is exactly the same size.
Your scheme may have some properties that can be compared with a hash based PRNG


Explanation of each of the parameters used in ECC

I know that k is what is used as the secret key and that $Q=(Q_x,Q_y)$ is the public key. But playing around on these two pages and seeing the contents of this file have letft me more confused. What is the importance of $P$ and how does it differ from $Q$?

Don't get too caught up with variable names. People usually use $P$ and $Q$ to represent points in general. There's really no notation that says $Q$ is always the public key.

The contents of that github file are parameters for Dual EC DRBG, which uses two points $P$ and $Q$, which are related. They're not public keys (atleast in the typical sense).

  Do a and b change depending on the key in question or are they held constant for a curve?

No. $a$, $b$, and $p$ define the curve and do not change.

  What is the function of n? It always seems to be slightly less in value than p. How do G, the order of the curve, and the seed fit in?

$n$ is the order of the point $G$. Simply put, it's the number of possible points you can generate through multiplication of $G$.

The private key $k$ is $1 \lt k \lt n$. If $k \geq n$ then it's effectively $k \mod n$. So another way to look at $n$ is the number of possible private keys. That's why when we generate curve parameters we want good parameters that give us a large $n$.

The seed is simply the seed for the random number generate that generated the parameters. This is used to show that the numbers were actually generated randomly.

  Finally, how is a number encrypted? Is it done by multiplying Q?

ECC isn't like RSA where you can encrypt a number directly. For encrypting with ECC you basically do half a key exchange by generating a shared secret using the sender's private key and the recipients public key. The sender encrypts the message using this shared secret. The recipient can reconstruct the shared secret key using their private key and the sender's public key, and can decrypt the message.

One common method is ECIES.

  And how can I extract the coordinates of Q from its "compact" form used in certficates?

A coordinate in compressed form will be the $X$ value, a value indicating whether to use the positive or negative $Y$ value. You just need to plug the $X$ value into the equation $Y = \sqrt{x^{3} + ax + b}$. There are algorithms to compute square roots $\mod p$.


How can I encrypt more than 64 bit with the Data Encryption Standard?

Well, the methods we use to take a block cipher (such as DES), and turn it into an actually useful function (say, to encrypt a large message) is called a mode of operation.

Such a mode of operation takes the message (generally of arbitrary length), and processes it (usually block by block), using the block cipher as a primitive.

There are a number of such modes of operation, the most popular of which are CBC mode and counter mode.  BTW: the mode where you just send the message in pieces to the block cipher in 64 bit chunks (and the encrypted message is just the output of the block cipher) is referred to as ECB mode – that is rarely appropriate (and certainly never unless you know what you're doing).

As for which mode would be appropriate for you, well, I can't answer that without knowing more about your application (and the security properties you need).

In addition, you say that you are intending to use DES.  DES is generally frowned upon nowadays (machines to break it are known to exist); the block cipher AES is usually a better choice (it is about as efficient in software, and it is currently believed to be secure).


Does a break in a collision resistance property of a hash function by definition implies an attack at the first pre-image attack?

This relation obviously doesn't hold.

If you define "break" as faster than what's expected of an ideal hash function

Define TrivialCollisionHash = GoodHash(input.Skip(1 bit)). Finding pre-images for this is just as hard as for GoodHash, i.e. $2^n$. Finding a collision is trivial, just flip the first bit.

If you define "break" as faster than a certain computation bound

Use an ideal hash function. It has collision resistance of $2^{n/2}$ and first pre-image resistance of $2^n$. So an attacker with a computational bound between $2^{n/2}$ and $2^n$ can find collisions but not pre-images. For example an attacker who can perform $2^{160}$ oracle queries on a 256 bit hash function will most likely find a collision, but he probably won't find a pre-image.


Security requirements for EC Diffie Hellman implementation

Here's the obvious advice (other than "don't roll your own protocol/solution; reuse one that has already been vetted"):

Make sure that you use a secure curve.  Obvious alternatives are P256 (with possible P224 or P192 if you need better performance, and don't mind cutting into the security somewhat), or (if you don't trust the US Government) a NUMS curve or a Brainpool curve.  Normally, I'd suggest Curve25519; however if you have a crypto accelerator that's targeted towards arbitrary curves in Weierstrass form, well, it could do Curve25519, but it's more hassle, and you lose the advantages you normally gain from Curve25519.
Make sure that you use a large sized private multiplier; for P256 (or any other curve based on a 256 bit prime), that means a 256 bit multiplier (and note: this doesn't mean that the 255th bit must be set; it means that all values between 1 and $2^{256}$ are possible).  You can make things go a bit faster if you use a smaller range, however that also cuts into the security.
Both sides need good entropy; if the attacker can guess the private multiplier of either side (or even reduce it to a not-huge subspace), he can recover the shared secret.
Validate the point that you receive from the other side, that it is a point on the curve; for example, if the other side sends both $x$ and $y$ coordinates, make sure that when you plug them into the Elliptic Curve equation, both sides evaluate to the same value.  There are cases where you can skip this (for example, if you use "point compression", or if you always generate a fresh random private multiplier for each exchange), however it's so cheap that it just makes sense.
Use a good KDF to convert the ECDH shared secret into the keys that you'll actually use.
Remember that ECDH does not authenticate who you're actually talking to.  Unless no one other than the person you're talking to can possible send (or modify) a message to you, you need a way to authenticate the other side.


reducing false positives in searchable encryption

Additional Storage approach

A trivial way is with additional storage. by making the $l$ to be complete string instead of few $left$ bits shown in the figure above. so technically $|l|=|n|$ and $|m| = 0$.

This way the entire string is covered for search. Now rest of the scheme is same except that the stream cipher bits $S_i$ in the figure above are $\oplus$'ed with entire $l_i$ and store the encryption of $F_{ki}(S_i)$ separately for matching. Now there is an additional over head of storing $F_{ki}(S_i)$ bits. In reality, if we use AES for $F_{ki}(S_i)$ operation would result in 128 bits additionally which might be an over kill. If we use some length preserving encryption like FNR we could reduce the size of additional storage needed to size of word itself. Even in this case, we need double the storage of input text as premium for reducing false positives.

Not sure of any other approaches so far. I have made a quick proof-of-concept which could be found here. The test cases written for both that has false positives and also that will not have any but needs additional storage


How secure is a password generator that runs SHA256 on a passphrase

Password managers with similar schemes do exist, and are called "deterministic password managers". While the idea does generally does work, this blog post names some rather big practical disadvantages, two of which I'll summarize:

Possibility of master passphrase compromise: If your master secret is ever compromised, all your passwords are now immediately compromised. Compare a classical, disk-based password manager: Here, an attacker would need access to the file as well as to the master passphrase.
Also, with just access to a single password (as well its seed, i.e. which site is was used for), an attacker can start trying to crack the master passphrase by brute-force. Especially a fast hash function like SHA256 instead of a purposefully slow key derivation function like Argon2 or PBKDF means that your master passphrase better be really good - so it would be advisable to use a randomly generated cryptographic key instead of a human-generated password*. This key would need to be stored somewhere, defeating the whole point of the scheme.

Without stored state, you loose some very important functionality: Once generated, it's now impossible to change a password, without memorizing a changed seed. For example, if your facebook password got compromised, you'd now have to remember typing in "facebook1" instead of "facebook". This is bad, because it discourages users from changing passwords they suspect might have been compromised.
Additionally, password requirements differ from site to site. Some might require special characters, some might forbid them altogether. To accommodate this, you'll also have to remember the exact password generator settings for each website.

In conclusion, your idea is probably sound from a cryptographic standpoint, but only as long as the master passphrase contains enough entropy (that amount being substantially higher than for online-brute-force-only attack scenarios). But in the real world, there are a lot of security and usability considerations making it generally not very practical, compared to a normal password manager.
* Of course, one could generate a rather long random passphrase that is both high-entropy and human-readable. But it might very well exceed your expectations for what is a reasonable length for a password.


Is there a cryptographic algorithm which is immune to side channel attacks?

A cryptographical algorithm can't be immune or not immune to side channel attacks; this is because a side channel attack attacks the implementation and not the actual algorithm.  Any algorithm that uses secret data can be implemented in a way that has side channel attacks, and any algorithm can be implemented in a way that may be resistant (the hard-core side channel attack guys will say that no implementation is totally immune) to side channel attacks.

That said, there are certainly algorithms that are easier to implement in a way that resists side channel attacks.


There are two ways a cipher can be broken: theoretically and practically. If the paper is correct then:

  Our fastest attack achieves a nearly feasible $T=2^{101}$ (cf. Section 28.6 and [28]). (emphasis mine)

If we verify this claim then we get:

  If we have a diverse population of at least $2^{79}$ diﬀerent 256-bit GOST keys generated at random, with access to $2^{32}$ CP per key, one can recover one of these 256-bit keys in total overall time of about $2^{101}$ GOST encryptions.

Now theoretically a cipher is broken if there is an attack that is (significantly) faster than brute force. Simply said, $2^{101}$ is a darn amount better than $2^{255}$ required for brute force. So if this claim is correct then the theoretical security of GOST is much lower than it is supposed to be. Hence it could be called broken.

Of course, nobody is going to invest that amount of memory or processing power to even prove this point. SHA-1 has a much lower effective security margin and it took a very long time before a collision could be found.

Given the structure of the paper I would say that it's likely that the claims are correct. That doesn't mean that anybody can now attack GOST. It does show that too many kinds of attack are possible. These kind of attacks will only get stronger. This is a clear indication that it would be wise to upgrade. The block size of 64 bit is also a good reason to upgrade, 64 bit is considered on the low side for many applications of block ciphers.

That all said, these specific cryptographic attacks can not be used to attack any well designed / implemented protocol that makes use of GOST. 101 bit security is generally thought to be out of reach, i.e. the "nearly feasible" in the text.


Is this DH variant a workable zero knowledge proof?

why it might be problematic to do this in practice.

One issue with it is that it potentially allows the attacker an Oracle to the cDH problem.

For example, suppose the Prover uses his $g^x$ value as his key share with a DH key exchange with Alice, who sends $g^a$, and both sides arrive at the $g^{ax}$ secret value.

Then, what your protocol would allow an evil Verifier to do is ask the Prover to prove that he knows $x$, and submits $g^a$ (or a blinded version) as his challenge; the Prover sends back $(g^a)^x$, and that gives away the secret value.


Why don't crypto-currencies use the Lamport signature scheme?

The major issue will be size difference. The size of ECDSA in bitcoin is much less than the Lamport Signature.

For ECDSA in bitcoin

The public key is only 33 Bytes (1 byte for prefix, and 32 bytes for 256-bit integer x)
Signature is at maximum 73 bytes

Whereas in Lamport Signature

The public key is 512 numbers of 256-bit (total of 16KB)
The Signature is 256 number of 256-bit (total of 8KB)

The size of Lamport public key and signature together is 231 times (106 bytes vs 24KB) more than the ECDSA public key and signature.

The public key and signature form part of each bitcoin transaction and are stored in block chain. So use of Lamport Signature will need 231 times more storage than ECDSA. As of 1 Oct 2017, the Blockchain size is approximately 135GB. Had it been the Lamport Signature, this would have been in TeraBytes. This would have resulted in higher storage and bandwidth requirement, less number of transactions in one block(which may create backlog, as one block is committed in 10 minutes) and more time in blockchain propagation to other nodes.

Moreover, In bitcoin each transaction is charged a network fee based upon transaction size(in terms of bytes, not in terms of amount). At the moment, the network fee rate is 178, 149, 120 satoshi / byte for high, medium and low priority respectively.


Zodiac unsolved 340 cipher decryption in 2020

It seems this is now cracked, see for example here.


Regarding step (3) on the computation of r = v - a * c mod n it
  means that this step is using regular modular arithmetic?

Yes.

  Is the following equivalent: V = ed25519_scalarmult(r, ED25519-BASE) +
  ed25519_scalarmult(c, A) [...]?

Yes, see also section 1.2 (near the end) where it says "P x [b]: multiplication of a point P with a scalar b over E(Fp)".

  And most importantly that + is Ed25519 point addition?

Yes, that is indeed the case, + represents the group operation here, which is modular-reduced multiplication for the finite field and point-addition for the EC case. This can be seen when looking at section 2.2.

  V = G x [r] + A x [c], can you please explain how that would hold?

I'll use a slightly more tense notation ($\xleftarrow{\$}$ means that the variable on the left is sampled uniformly at random from the set on the right).

Pick and publish your public key $A=[a]G$ with $a\xleftarrow{\$}\{1,...,n-1\}$
Pick $v\xleftarrow{\$}\{1,...,n-1\}$, send $V=[v]G$.
Pick $c\xleftarrow{\$}\{1,..,2^t-1\}$, for some security parameter $t$, send $c$
Compute $r=v-a\cdot c\bmod n$ and send $r$.

Now the question is why $V=[r]G+[c]A$ holds in an honest protocol execution. Well $$[c]A+[r]G=[c\cdot a]G+[v-a\cdot c]G=[c\cdot a+v-a\cdot c]G=[v]G=V$$


Why is the signatureAlgorithm field in X.509 certificates redundant?

From RFC 5280 r.e TBSCertificate.signature

  This field contains the algorithm identifier for the algorithm used
     by the CA to sign the certificate.

  This field MUST contain the same algorithm identifier as the
     signatureAlgorithm field in the sequence Certificate (Section 4.1.1.2).

I think it's because the authoritative signature is on the contents of TBSCertificate. If the signature algorithm used by the CA weren't included in the certificate to be signed then maybe one could change the Certificate.signatureAlgorithm field to something more amenable to a would-be adversary.

A similar answer has been given before on security.SE


Why $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ for RSA crypto?

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that:

any small odd $e>2$ (including the common $e=3$ and $e=65537$) is a usable public exponent (because then, $e$ does not divide $p-1$ or $q-1$);
Pollard's $p−1$ factoring algorithm will be ineffective, because it depends on the integer $n$ being factored having a factor $p$ with $p-1$ a smooth integer.

In RSA as usually practiced, it is generally enough to use huge random primes for $p$ and $q$. However, for relatively small modulus it is customary to require that $p-1$, $q-1$, $p+1$, and $q+1$ have one big prime factor, in order to ensure that Pollard's $p−1$ and William's $p+1$ factoring algorithms are less efficient than ECM; that precaution was mandated by ANSI X9.31, and is still in FIPS 186-4 for all $1024$ bit modulus and some prime generation methods; I believe (against the advice of many) that it remains useful when one considers an adversary content with factoring one public modulus among many.

As pointed by DrLecter, RSA-like cryptosystems or protocols using a key similar to RSA may have additional requirements; see his answer.


Blum Blum Shub vs. AES-CTR or other CSPRNGs

Blum-Blum-Shub is a stream cipher: given a short key, it produces an effectively unlimited-length stream of pseudorandom bits.  Other well-known examples of stream ciphers include AES-CTR and RC4.

Blum-Blum-Shub gets mentioned a lot by non-expert cryptographers.  I suspect this is because it comes with a "proof" of security, which sounds like a wonderful thing to have.  It might not hurt that BBS was mentioned in Applied Cryptography, and some developers may have walked away from that thinking that BBS is the bee's knees.

However, I personally don't recommend BBS.  The proof of security turns out to be highly misleading, and it comes with some fine print that makes the proof close to useless in practice.  You are probably better off using AES-CTR (AES in counter mode).  AES has been carefully vetted and is widely trusted.  AES-CTR should provide excellent security -- while also providing excellent performance.

BBS has two problems:

BBS is very slow -- excruciatingly slow.
Also, the existence of the "proof of security" is highly misleading and usually misinterpreted.  Practical folks almost always draw the wrong conclusions from the "proof of security".

These two problems are linked.   The standard proof of security says that if you choose a modulus N that is large enough, then no attacker will be able to efficiently break BBS.  However, the standard proof does not say how large N has to be, to achieve any desired level of security.  More recently, researchers have worked out how large a modulus you need, and (here comes the fine print:) it turns out N needs to be ridiculously large to have any decent level of provable security.  I'll summarize some of their results below:

Result 1. Suppose you use BBS with a 768-bit modulus.  You've read that 768 bits is enough to make factoring infeasible, so this sounds peachy.  You've read that it is safe to extract O(lg n) bits in each iteration; here n = 768, and lg n = 9.58, so you decide to extract 9 bits in each iteration.  You use it to generate a pseudorandom stream of 107 bits (about 1MB of pseudorandom data).  How much security do you get?  Answer: the security proof guarantees security against any adversary that uses at most 2-264 steps of computation.  Yes, this is an utterly ridiculous and useless statement!  To put it in plain English, the security proof guarantees absolutely nothing useful at all.

The lessons is: With natural-sized parameters, there is no guarantee that your use of BBS will be secure in practice.  The "proof of security" is useless for ordinary-sized parameters.

Result 2. Suppose you learn about this result, and decide to use a longer modulus.  Suppose you decide to use BBS with a 6800-bit modulus, and extract 5 bits on each iteration.  Suppose you extract no more than one million pseudorandom bits from the BBS generator.  Then, there is a proof showing that it will take at least 2100 steps of computation to break BBS (given plausible assumptions).  This means you should have a reasonable level of security.  My estimate is that, on my machine, producing one million bits (128KB) of output with BBS would take about 5-10 minutes, whereas with AES-CTR it would take less than a second.

In other words, to achieve even a mild degree of security in practice, BBS needs an enormous modulus -- far long than anything you'd use with RSA.  This large modulus makes BBS very slow.  It's far slower than AES -- and probably far weaker, too, as AES is believed to be safe for use even if you extract far more than one million bits of pseudorandom output.

Result 3. Here's another way to think about it.  A third researcher worked out the ratio in level of security between BBS and factoring.  He found that it's possible that there could be an attack that breaks BBS and is 1054 n3 times faster than any algorithm for factoring algorithm (for factoring the BBS modulus).  For instance, for a 1024-bit modulus (n = 1024), someone might be able to break BBS 1063 times as fast as they can factor.  Since we know you can factor a 1024-bit modulus with fewer than 1024 steps of computation, this guarantee about 1024-bit BBS is utterly useless: it is no guarantee of security at all.

As another example, for a 8192-bit modulus, the result says that there might be some clever algorithm for breaking BBS up to 1065 times faster than we know how to factor a 8192-bit modulus.  This is a huge ratio.  It says that BBS might be far easier to break than RSA is.  It means our proof of security for BBS is meaningful only if we use an enormous modulus, and only if we believe that factoring a modulus of that size is stupendously hard.  If we're willing to assume that factoring such a modulus is stupendously hard, we can deduce that breaking BBS is pretty hard; but because we need to use such an enormous modulus, the resulting BBS scheme will be enormously slow.

For more details, see the following research papers:

Another Look at Tightness, Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar, Selected Areas in Cryptography 2011.
Concrete Security of the Blum-Blum-Shub Pseudorandom Generator, Andrey Sidorenko and Berry Schoenmakers, Cryptography and Coding 2005.
and, this sci.crypt post from Dan Bernstein: Re: BBS PRNG strength recommendation parameters

Footnote on terminology: Theorists sometimes call stream ciphers by the name "pseudorandom generators" (PRGs).  Confusingly, this is not the same as a "pseudorandom number generator" (PRNG).

The term "pseudorandom number generator" (PRNG) is not always used consistently.  There are two possible meanings.  Some folks use it as a synonym for stream cipher.  Personally, I prefer to reserve PRNG for a scheme that is used to generate pseudorandom numbers, using no explicit input (but somehow gathering entropy from the environment).  With my preferred terminology, you use a PRNG to generate a short cryptographic key; then you use a stream cipher (a PRG) to stretch the short crypto key into a very long keystream of pseudorandom bits.  But others use the term differently.

Given this opportunity for confusion, if the meaning of the term is not clear from context, it may be best to avoid the term PRNG.


How to exchange keys despite a MITM, using some short known password?

This is called the Socialist Millionaire Problem. A solution for it exists, as published in this paper.
According to Wikipedia:

It is often used as a cryptographic protocol that allows two parties to verify the identity of the remote party through the use of a shared secret, avoiding a man-in-the-middle attack without the inconvenience of manually comparing public key fingerprints through an outside channel. In effect, a relatively weak password/passphrase in natural language can be used.

The protocol allows two parties to know whether or not they both share the same secret, such as a password, without transmitting it. If the other side, which may be an MITM attacker, is not able to prove that it has the same secret, then the session can be terminated before sending any sensitive information. Neither side learns any information about the secret in the process, other than the fact that the shared secrets did not match. If it succeeds and they do match, then they're MITM-free.
This technique is used in the OTR protocol. Unauthenticated Diffie-Hellman key exchange is done first, after which SMP is performed within the encrypted channel. Further communication is denied unless the other side can prove that it shares the same secret and thus is not an MITM attacker. In order to successfully perform an MITM attack, the attacker would need to either correctly guess the shared secret in its entirety by performing multiple connection attempts and re-trying on each failure without alerting anyone to the attack, or solve the discrete logarithm problem (DLP) that underlies Diffie-Hellman security, which is currently thought to be hard when correct parameters are chosen.
A simplified explanation of the protocol and its properties as used in OTR is available here.


does re-encrypting the same value with multiple keys reduce security

Does re-encrypting the same value with multiple keys reduce security?

The answer is "it depends"; there are some attack models and encryption methods where the security is reduced, there are other cases where there appears to be no security reduction.

Let us go through some models where we actually see a security reduction:

Plaintext guessing attack and deterministic encryption

In this attack model, the attacker has a guess to the plaintext $P_{guess}$ and wants to confirm whether $P_1 \stackrel{?}{=} P_{guess}$.  What he can do is guess random keys $K_{guess}$ and compute $E_{K_{guess}}(P_{guess})$ and he if that appears in one of the ciphertexts he's been given.  If he happens to guess a key $K_i$, then ciphertext $C_i$ will match, and he will get confirmation that his guess is likely to be correct - that's because we assume that the encryption is deterministic and so if the keys and the plaintext match, the ciphertext will as well.  Obviously, using more keys means that there are more targets the attacker can stumble into.

Deterministic stream ciphers, and plaintext with known linear relations.

Here, we assume we don't know the plaintext, however we do know certain linear relations between the bits of the plaintext; for example, we may know that the parity of each byte is even.  We also assume that the cipher works by generating a keystream (as a function of the key), and then exclusive-or the keystream with the plaintext to form the ciphertext.

So, what the attacker can do is examine each ciphertext; by assuming that the linear relationships hold in the original plaintext, he can evaluate the corresponding linear functions on the keystream; in the example, he can compute the parity of each byte of the keystream.

Then, he can pick random keys, and generate the corresponding keystream (here, we assume that this is determanistic).  Then, he can compute the linear function of that keystream (in the example, the parity of each byte), and see if it matches one of the keystreams that correspond to the known ciphertexts.

Like the first example, having more targets makes it more likely that the attacker will guess the correct key.

(Also, if you think that the example of "parity of each byte is even" is contrived, a more realistic example is "the msbit of each byte is 0").

Deterministic RSA encryption

If the encrypt the exact same message (without padding, or using determanistic padding) to $n$ different keys, and $n \ge e$ (where $e$ is the common public exponent), then it's easy to recover the message.  This is typically used as an example why you need to add randomness to your RSA encryption, even if you don't care about plaintext guessing attacks.

The above are three examples where encrypting with multiple keys can reduce security; in other cases (such as CBC-mode encryption), there is no obvious way to use multiple ciphertexts.

Now, the obvious thing about all three examples are that they are deterministic encryption; it would appear to be wise to add randomness if you are encrypting with multiple keys.


Probability amplication in OWF without hardcore bits

No it doesn't.

The problem with the approach you suggest appears if you write down formally what you suggest: you want to repeat many times each predictor, and evaluate a majority over their predictions. However, the randomness must be taken over a random choice of input. Your predictors give approximately good answers, when averaging over all inputs to $f$. This means that there is no way to implement the strategy you suggest for a fixed input $x$.

Essentially, you can imagine a OWF where each $i$th bit predictor would give a good answer for a non-negligible fraction of the inputs (say, some subset $S_i$ of the domain of $f$), but that does not mean that inputs from $S_i$ are inputs for which the other predictors will give good results.

Here is a quick counter example: suppose that we have a length-preserving OWF $g$, with domain $\{0,1\}^n$, whose outputs are uniformly distributed. You can construct such a function easily using a PRG, which in turn can be based on any OWF. Now, let $f$ be defined as follow: consider a natural ordering of the bitstrings in $\{0,1\}^n$, and divide the domain in $n$ blocks $(B_1, \ldots, B_n)$, each containing $2^n/n$ strings. On input $x$, we define $f(x)$ to be the value obtained by replacing the $i$th bit of $g(x)$ by $0$ if the $i$th bit of $x$ is $0$, where $i$ is the index of the block $B_i$ that $x$ belongs to.

I claim that $f$ is one-way if $g$ is. Here is why: on a challenge $y$, given access to an algorithm $A$ that inverts $g$ with non-negligible probability, call $A$ on all values $(y_0,\ldots,y_n)$, where $y_i$ is obtained by replacing the $i$th bit of $y$ by $1$ (and $y_0$ is just $y$). When receiving $A$'th answers $(x_0,\ldots,x_n)$, evaluate $f$ on $(x_0,\ldots,x_n)$; if one of the evaluations (say, on $x_i$) returns $y$, stop and return $x_i$; otherwise, return $\bot$. As one of the $y_i$ is exactly the correct output of $g$ on a preimage of $y$ by $f$, it is easy to see that the probability of successfully inverting is exactly the success probability of $A$.

I claim that there are predictors $P_i$ predicting the $i$th bit of $x$ with non-negligible probability. $P_i$ simply works as follows: on input $y$, return the $i$th bit of $y$. Why does it work? Because a random input belongs to $B_i$ and has his $i$th bit equal to $0$ with probability $1/2n$, in which case the $i$th bit of the output is $0$ and the predictor always succeeds. Otherwise, the $i$th bit is uniformly distributed and the predictor succeeds with probability $1/2$, hence it has non-negligible success probability overall.


Client-side password stretching - danger of the salt being public?

Though the salt is not considered a real "secret", is having the salt
  that public a serious consideration for rejecting this method (i.e.
  client-side password stretching)?

Yes, it is better if the salt is kept secret, but the attacker still has to perform a full-on offline brute-force search even if they know the salt before a breach, it's just that this search can be carried out before a breach and then after a breach only a logarithmic effort per entry is needed for the lookups. And if they don't learn the salt, the "timer" at which brute-forcing starts is pushed back to the point where the database leaks.

Now this exact attack, the ability to pre-compute real-salt-based password hashes before an actual breach is part of the reason why OPAQUE, the current state-of-the-art asymmetric password-authenticated key exchange (aPAKE) exists, as no previous aPAKE defended against this kind of attack.

So TL;DR: Hiding the salt is better, but actually doing so may be considered too much work and it's not the end of the world if the salt leaks.


A quick Google search shows the source code is available in the file dbmsrand.sql, which says:

-- Delayed Fibonacci, pilfered from Knuth volume 2


What are recommended, general strategies to start block-cipher design and/or analysis?

In order to design and analyze a cipher, we have to establish what a cipher is supposed to accomplish. Put simply, we would like to be able to transform information in such a way that only those who are authorized may perform or invert the transformation. We can refer to this transformation as "encryption". Unauthorized parties may exist that should not be able to obtain any information protected by the encryption method, despite the fact that they can/will try to do so, if given the opportunity. This applies even if the work that would be involved is a large, nontrivial amount. We can refer to unauthorized parties as adversaries.

Ideally, we would like the mutual information required by the authorized parties to be minimal, and for it to be obtainable with some level of convenience. If it were not for these two extremely practical aspects, the One Time Pad  would be literally unbeatable, with information-theoretic security, implementation simplicity, and maximum efficiency (just a single addition per character!). A OTP is not a block cipher, but it makes for a good reference point to measure against.

Unfortunately, one time pads require the key material be as long as the information to be enciphered, and prepared ahead of time by the authorized parties. This violates our two practical desires listed above, so we must design other algorithms that can re-use a much smaller key.

One temptation is to keep the encryption algorithm itself secret. Unfortunately, keeping an algorithm secret implies that all users of the algorithm know the secret to encrypting/decrypting. As the number of users that know the secret increases, so does the likelihood that the secret will become compromised by adversaries. This would fail the original design goal, and only does marginally better then the OTP in terms of practicality and the size of the secret to be protected.

This leads to the third, most successful option: Using a publicly known algorithm that concentrates the required secrecy into a key that is used by the algorithm.

Whatever method is used to encrypt, the information may be subject to attack by adversaries. The job of encryption is to resist this attack, and keep the information protected. This means a few things:

Since modern ciphers use a key to authorize parties to perform the transformation, the goal of an adversary is to obtain the key

Obtaining the key implies the ability to encrypt plaintexts and decrypt ciphertexts, violating the original design goal of the cipher

Similar to how a lock on a door uses a key
You just have to protect the key, not prevent anyone from knowing there is a lock
The key is reusable, and has a very long lifespan.
The key should be relatively small - 128 to 256 bits is common

The key must remain secure even if the adversary:

Possesses vast amounts of ciphertext
Knows the plaintext contents of a message, and the corresponding ciphertexts for each message
Can trick an authorized party into encrypting/decrypting messages for the adversary

Choose messages to encrypt or decrypt at will.
Can adapt or modify future encryption/decryption queries in response to past queries.

Most of the complexity of a modern cipher comes from the attempt at protecting the key, and by extension, the plaintext. Designing a cipher with a reusable key will require an understanding of the ways that the cipher and key can be attacked. In order to design a cipher, you must learn to think like the adversary, and study how ciphers are broken.

Standard attacks

There are a handful of generic attack methods that any new cipher must protect against: brute force search, differential cryptanalysis, and linear cryptanalysis.

Brute force search means that the adversary simply guesses all possible combinations of key values, until the correct key is found

Has a worst case time complexity of $2^N$, where $N$ is the width of the key in bits

time complexity is only accurate if the key is uniformly random
64 bits is considered too low for modern computers
128 bits is considered secure for now
256 bits is considered secure forever, even in the face of futuristic quantum computers

Differential cryptanalysis exploits the probability that a particular difference ($\Delta_1$) between inputs ($t_1$ and $t_1'$) will be propagate to a particular output difference ($\Delta_2$)

By testing all the possible input differences, it is possible to return probabilities to have some output differences. A couple of specific differences $\Delta_1$ and $\Delta_2$ is called a differential and noted ($\Delta_1 \Rightarrow \Delta_2$).
The more likely that a given differential ($\Delta \Rightarrow \Delta'$) holds, the more effectively this behavior can be exploited against the cipher
A relatively simple tutorial with code can be found here
The original paper by Biham and Shamir can be found here

Linear cryptanalysis exploits the probability of a subsection of bits from a given input is correlated with a subsection of bits in the output of a function

A subsection of bits is selected via bitwise masking
The exploitable relationship is if the parity  of the hamming weight  of the subsection of input and output bits is the same
The more regularly this relationship occurs, the more effective linear cryptanalysis will be
A relatively simple tutorial with code can be found here
The original paper by Matsui can be found here

Linear and differential cryptanalysis can provide hints as to what the internal state of the cipher may be, up to a certain point. This can reduce the number of possible values for a part of the key that an adversary will have to guess. These are considered to be two of the most powerful tools in regards to cryptanalysis of a modern cipher.

Block Cipher constructions

There are two main classes of cipher constructions: The Feistel network , and the substitution-permutation network.

The basic design of the Feistel network is to split the message block into two halves, a left and a right. A keyed function with good diffusion and confusion is applied to right half, and the output of this is added to the left half. The halves are then swapped, and the process repeated. Decryption is more or less the same operation performed with the reverse keys, and so this construction is relatively lightweight in terms of implementation complexity. DES is an example of a Feistel network. There are differential and linear attacks against DES.

The design of a substitution permutation network is typically finer grain then a left and right half of a Feistel network. For example, in the Rijndael cipher, also known as Advanced Encryption Standard (AES), the message is operated upon as 16 x 1 byte state, arranged as 4 rows and 4 columns. It consists of 4 main steps: a byte substitution, a row transposition, a mixColumns step, and the addition of key material via XOR.

Many, if not all modern block ciphers, are made of repeatedly iterating the same core function(s), often times with multiple different keys between each application. Often times, these keys are derived from the master key that is actually supplied to the cipher by the user. We refer to keys generated this way as the round keys, and the process of generating them the key schedule.

The way round keys are derived can influence both the security and efficiency of the cipher. Ideally, recovery of any round key information should reveal as little as possible about other rounds keys or the master key. This is one of the strengths of the OTP: recovery of a byte of key material (i.e. via known plaintext attack) provides no assistance in the recovery of any other bytes of the key. It is also generally considered beneficial for the generation of round key material to be quick, as a cipher with a slow key schedule may have greater latency and/or lower throughput.

Designing a round function

In order to know what to operations to use, we need to know what we need to accomplish:

Diffusion

Flipping one input bit anywhere should flip (about) half the output bits on average
Bytewise shifts, rotations, and transpositions can help spread the influence of a given subsection of bits
Bitwise transpositions can be used too, but can be relatively slow in software (but potentially fast in hardware)

Confusion/Non-linearity

The relationship between the key and ciphertext should be complex
A linear cipher can be broken by gaussian elimination
Mixing arithmetic in different fields can provide non-linearity (i.e. xor and addition modulo 256)
Boolean functions can provide non-linearity

Invertible only with the correct key

The cipher will only provide confidentiality if secret (key) material is introduced at some point.

Applying a key on the input before applying any rounds and after applying all rounds is called key whitening and is common
Additionally, a key is added every N rounds, where N is often 1 (i.e. after every round)
Key addition is often times done via xor and addition modulo (2**wordsize_in_bits), or both

There should be no "weak keys"

So our goals are to combine the message with a key, and flip lots of bits in a diffusing and non-linear fashion.
Ideally, we would like the composition of our operations to produce output similar to that of a random permutation.

Some available instructions are:

Xor

Useful for combining two inputs (i.e. message and key)
Is its own inverse (an involution)

No subtraction instruction required to invert

Bit sliced
Needs addition/boolean function/s-box lookup for non-linearity

Addition

Useful for combining two inputs
Requires separate subtraction instruction to invert
Tends to flip low order bits more then high order bits

Lookup tables

Useful for good differential/linear properties
Effectively equivalent to the cached inputs/outputs of a non-linear function
Can be vulnerable to timing attacks on machines that utilize a cache

Boolean functions

Useful for non-linearity
Some examples are the Choice and Majority functions

Choice

Logically, If C then B, else A
c ^ (a & (b ^ c)) (for mathematicans: $c\oplus(a\wedge(b\oplus c))$ )
Bit sliced operation

Majority

(a & b) | (a & c) | (b & c) (for mathematicans: $(a\wedge b)\vee(a\wedge c)\vee(b\wedge c)$ )

Rotations/Shifts

Useful for diffusion and carrying/spreading differences through a word
Generally done by fixed amounts, but not necessarily

Transposition

Shuffling the order of state words can help provide diffusion
Transposing bytes according to secret data can be vulnerable to timing attacks (secret dependent memory access is the concern)
Includes rotations

Composed bitwise and bytewise transposition:

Acts like a shuffle (permutation) of the input bits
Only modifies a given bits position, not its value (Does not modify hamming weight)
Is a linear transformation
Example: The Keccak permutation, specifically the Rho and Pi steps
Can provide "weak alignment"

Pseudo-Hadamard transform:

Provides diffusion
Used by SAFER and Twofish

Some example combinations of the above operations:

Rijndael consists of addRoundKey, mixColumns, shiftRows, subBytes on the message:

subBytes is a lookup table (good differential/linear properties)
shiftRows is a bytewise transposition
mixColumns is a linear transformation that, in conjunction with shiftRows, provides diffusion
addRoundKey xors the key with the state

DES round function consists of an expansion permutation, key mixing, s-box application, and bit permutation

Expansion compensates the S-boxes going from 6 to 4 bits.
Keys are applied every round via xor
S-boxes provide resistance against differential cryptanalysis
Bit permutation provides diffusion

Serpent round function consists of key-mixing XOR, a 4×4 S-box, and a linear transformation

Keys are applied every round via xor
S-boxes are applied in parallel (bit sliced design)
Linear mixing provides diffusion

TEA uses only addition, shift, and XOR:

xor/addition create nonlinearity and apply key material
shifts/additions provide diffusion

As we can see from some examples, there appear to be at least two different approaches:

S-box based designs

Can offer very good linear/differential properties with good performance
Can be hard to find good large s-boxes because of the huge search space
Tend to be used in conjunction with a linear mixing layer for diffusion
Rijndael strategy:

Use an s-box with the optimal worst case differential/linear properties
Use a mixing layer that aims at increase the lower bound of the rate of diffusion
Notice how it's designed around the worst case scenario

Can provide clear proofs of resistance to differential/linear attack

ARX based designs (addition, rotation, xor)

Are inherently less conducive to timing based side channel attacks then s-box based constructions

Addition, XOR and rotation by fixed amount are often times implemented in constant time

Fast performance on PCs (especially if you can avoid memory accesses/stick to the registers)
Compact/simple implementation (does not require the space that lookup tables need)
Not as straightforward to analyze security to differential/linear attack compared to s-box based design

Many ciphers use a set of constants. Every round, a new constant is introduced to the state via addition/xor. This can help against slide attacks by making successive rounds different.

Breaking a round function

Before you resort to applying linear and/or differential cryptanalysis to any new design, considering running some statistical tests. Statistical tests can tell you very quickly whether your latest design is totally broken. Note that statistical tests cannot confirm whether a design is cryptographically secure, it can only confirm that a design is insecure.

Some example tests might be:

Avalanche test

Generate blocks of random data with a given key (i.e. encrypt an incrementing counter) and measure the hamming distance between successive outputs (measures diffusion of data)
Encrypt the same series of successive values with a different key, and measure the hamming distance between the previous set of random data and the new set (measures diffusion of key)

Randomness test

Generate a sizeable (>1MB) amount of psuedorandom data with the cipher (i.e. by encrypting an incrementing counter)
Pass the data to a tool such as ent, dieharder, or the NIST test suite

Run the mentioned tests on both your design and on os.urandom: ideally the two results should be indistinguishable.

When devising an attack, try attacking a reduced (single?) round version of the cipher first. Look for the weakest points in the design.
Try practising against FEAL, it has a major weak point and is useful for learning differential/linear cryptanalysis, and slide attacks.
Some of the attacks against DES would probably be helpful ways to learn about linear cryptanalysis and brute force search

Once you've got a handle on those, there are actually many different attacks besides generic linear/differential cryptanalysis
You may find some software related to cryptanalysis here

Math and visualization

If you find visualizations and diagrams helpful, this page may be interesting to you.
If you do not know math well, try learning some of the notation. Much of the information you want to understand will be in scientific research papers and written in the language of math.

Some of the subjects that will prove useful when reading papers and in cryptanalysis/cipher design are:

Basic Set theory
Basic Probability theory
Basic linear algebra
Boolean logic
Finite fields


How close to pure math is cryptographic theory?

Is cryptographic research in the same line as formal mathematical
  proof?

Not always, but the large area of provable security is. Provable security is (essentially) the task of formally proving theorems about crypto, which will in general be of the form "if this mathematical hypothesis is true, then this cryptographic primitive is secure against a given type of attack". Each time a new primitive is suggested to address some security requirement, it comes with proofs of theorems providing hindsights regarding the security of the scheme (though that's not always the case, especially with papers from the early days of crypto). An important part of cryptography is also about analyzing and implementing cryptographic protocols and primitives, but that does not mean all cryptographers do also implement crypto. In many labs, 95% of the work will involve essentially pen-and-paper analysis - although even the most theoretical works sometimes lead to result that one might want to implement, if only to see how efficient it is.

  Is there a need for abstract mathematics in modern cryptography?

Yes and no. A knowledge of the formalism in some area of abstract mathematics can help a lot into understanding and studying crypto, but in most cases, you will not need a deep knowledge of the most advanced results in abstract mathematics. For example, most results you would learn from an advanced math course about elliptic curves would be outside the scope of the background needed to understand elliptic-curve-based cryptography. Similarly, you would not need extremely advanced courses on algebra to understand the notions used in crypto (essentially, standard algebra results on finite fields and additive groups suffice for many things, plus some more crypto-related algebra result).

However, as is common in theoretical computer science, mathematics often show up unexpectedly when studying some problems, and relatively deep mathematical results can prove useful in the analysis of some cryptographic primitives. The first example that comes out of my head is this recent paper from ePrint (the crypto archive) which establishes lower bounds for a primitive known as order-revealing encryption (an encryption scheme that does not hide the result of the comparison between encrypted messages), and relies on (an extension of) a theorem of Erdös on tournament graphs.

The high level bit is: studying math is a very pertinent choice if you're planning to do theoretical crypto later, because being at ease with mathematical formalisms will make you way more comfortable than many with crypto. It is widely acknowledged in crypto that the field would benefit from having more mathematicians studying this area. However, do not expect your knowledge of advanced math results to be crucial to your work in crypto on a daily basis, and theoretical crypto in itself remains a science with its own formalisms and practices that you would have to study if you want to work in the field.


Since it's your homework, I'll only hive you the direction and not a full formal proof:

a) if at least one of H1 and H2 are collision resistant then H is too. Because if H is not coll-resistant then it's possible to find x and x' s.t. H(x)=H(x') so H(x)=H1(x)||H2(x)=H1(x')||H2(x')=H(x') which means that H1(x)=H1(x') and H2(x)=H2(x') so we found a collision in both H1 and H2.

b) About preimage res, if H is not preimage-res then given y it is possible to find x such that H(x)=y. We know that y=y1||y2=H1(x)||H2(x), thus you can find the preimage of y in both H1 and H2 as before.

c) about the composition, it is clear that a composition is also coll-res. Assume that H(H(•)) is not coll-res then it immediately means that H(•) is not coll-rea, by contradiction to the fact that H is coll-res.


What encryption/decryption method should I use when multiple users should have access to the encrypted information?

Here's an example scheme that should work with $\mathcal O(r)$ operations for $r$ registrations and $\mathcal O(n+r)$ operations for $n$ documents and $r$ revoked (simultaneously) user accounts, but of course would perform all (eg search) operations client-side. This also involves only $\mathcal O(n+r)$ keys. Doing something like this (securely, partially) server-side is possible but more complex, this is called searchable or structured encryption and allows you to eg search for specific keywords / tags without the server learning the precise keyswords. This is eg deployed by pixek (RWC 2018 slides PDF) where apparently these three schemes are used: One, Two, Three.

The initial setup goes like this:

Define a (random) symmetric key $K$ for the entire database.
Define a (random) symmetric key $K_i$ for the $i$-th document.
Encrypt the $i$-th document using $K_i$ and store $\operatorname{Enc}_K(K_i)$ "next to the document" ie so that you can find this ciphertext when you know which document to access.

The per-user registration goes like this:

Encrypt $K$ under a user-specific public key. This is what happens upon registration. This public key may be stored symmetrically encrypted on the server using the user's password.

Revokation then works like this:

Upon revokation pick a new $K'$. Re-encrypt all $K_i$ with that $K'$ and encrypt the new $K'$ under the public keys of all the users and replace the old encryptions of $K$.

Accessing a document then goes like this:

The user retrieves their private-public keypair.
The user requests their encrypted copy of $K$ and decrypts it.
The user requests a document with its encrypted per-document key, decrypts this key and decrypts the document.

Because this question will probably come up:

  Why not use the global key to encrypt all the documents directly?

The idea is to a) limit the amount of ciphertext available under a single key and b) that if some user has access, they learn $K$, and so you would have to actually re-encrypt all the documents after their access gets revoked in case an admin leaks the ciphertext blobs. If you also update the per-document key on each document update any user will only be able to decrypt documents they have already seen this way.


Need help to understand this RSA common modulus attack Python code

Step by step of the code;

$gcd = \gcd(e_1,e_2)$

$a = e_1^{-1} \bmod e_2$

$b =gcd - (a\cdot e_1))/e_2 \implies gcd = b \cdot e_2 + a\cdot e_1$; The Bézout's identity

$i = c_2^{-1} \bmod n$

$mx = c_1^a \bmod n$

$my = i^{-b} \bmod n$

$\text{return } (mx \cdot my) \bmod n$

Now check
\begin{align}
 mx \cdot my &=c_1^a \cdot i^{-b} \pmod n\\
  & = c_1^a \cdot (c_2^{-1})^{-b} \pmod n\\
  & =(m^{e_1})^a \cdot (m^{e_2})^{b} \pmod n\\
  & =(m^{e_1 a+ e_2 b}) \pmod n\\
  & = (m^{gcd})  & & \big[ = m \!\!\!\pmod n \,\textbf{ if } gcd=1\big]\\
\end{align}
The above calculation works for any $gcd$. This doesn't mean that we can resolve the message $m$ if $gcd>1$. What if $gcd \neq 1$ then for case 2, it is so-called Rabin Cryptosystem, security is shown to be equal to factoring. if $gcd =3$ is the cube-root attack possible and if the textbook RSA is used and the message $m < \sqrt[3]{n}$ recovery possible, and so on.
The conclusion is that they forget to write
  if gcd != 1:
      return -1

Writing good software is hard, writing good cryptographic software is much harder.
or someone is wrong on the internet

The common modulus attack is performed on Text-Book RSA when Alice and Bob use the same modulus $n$ with different public modulus. The first observation is that this is dangerous since Alice can learn Bob's private key, v.s. On the other hand, the eavesdropper ( passive attacker) knows the public keys $(n,e_1)$ and $(n,e_2)$ and when observed that the same message is sent to Alice and Bob (possibly broadcasting). Then the eavesdropper can resolve the broadcasted message $m$ if $\gcd(e_1,e_2)=1$. If they are using the same public exponent, this attack doesn't work.
When proper padding is used like PKCS#1 v1.5 and OAEP then this attack is not possible since they use randomization that prevents the equality of the same messages.


What is the default behaviour, if no ciphers are enabled

Will server use any null ciphers by default to complete the ssl
  handshake.

No. The TLS v1.0 specification explicitely states that the TLS_NULL_WITH_NULL_NULL cipher suite must not be negotiated. However, using a cipher suite that only offers authentication but no encryption is valid (and done in e.g. Windows Update). An example for such a suite is TLS_RSA_WITH_NULL_SHA.

To quote appendix A.5 of RFC2246:

  TLS_NULL_WITH_NULL_NULL is specified and is the initial state of a
  TLS connection during the first handshake on that channel, but must
  not be negotiated, as it provides no more protection than an
  unsecured connection.

$\space$

  Lets for example, a server is configured to use TLS1.0 and there is no
  ciphers enabled for it, what will be the default behaviour if a client
  connects to it.

It depends, either the server implementation will override your configuration and use the default list of accepted cipher suites, or it will refuse all incoming TLS connections because no client can offer an accepted cipher suite to the server (because it doesn't accept any).


Difference between linear cryptanalysis and differential cryptanalysis

Differential cryptanalysis works on differences. Linear cryptanalysis works on linearity. Neat, isn't it ?

Instead of speaking of how they differ, it is easier to list their common features. Both kinds of attacks:

Use a lot of known pairs plaintext/ciphertext (many input messages encrypted with the same key, and, for each of them, the attacker knows both the block value before encryption, and after).
Rely on an "approximation" of the internal behaviour of the encryption function, which holds with a small but non-zero probability for some input.
Work with detected weaknesses in the internal structure of the algorithm; they don't work "generically".

With differential cryptanalysis, the known plaintext/ciphertext pairs must be organized in pairs where both plaintexts differ by a specific difference ("difference" being a XOR, a subtraction... whatever works well algebraically with the algorithm at hand; for DES, this is XOR). The "approximation" is that this input difference will yield another specific difference on the output with a probability which is somewhat higher than what could be obtained with pure randomness, and the exact difference which will most probably appear depends on some of the key bits. Successful differential cryptanalysis normally requires chosen plaintext/ciphertext pairs (the attacker gets to choose the plaintexts or the ciphertexts).

With linear cryptanalysis, the approximation is a linear formula (i.e. a bunch of XOR on bits) which links together some input bits, some output bits and some key bits, with a probability somewhat higher than what could be obtained with pure random. This "linear formula" works best (i.e. is fulfilled most often) when the hypothesis on the involved key bits is correct, so the analysis yields a few key bits.

The most salient difference between linear and differential cryptanalysis is the known/chosen plaintext duality. For linear cryptanalysis, known random plaintexts are sufficient, but differential cryptanalysis requires chosen plaintexts, which, depending on the context, may or may not be a significant problem for the attacker.

Linear cryptanalysis is easier to grasp, so begin with that one. This PhD thesis is a nice introduction. For differential cryptanalysis, read this well-explained article.


Encrypt-then-MAC: full random keys or keys derived from master key?

If you are concerned about database size, only the master key needs to be stored when you use HKDF. Ditto when sending it to another computer. Otherwise, two independent random keys are clearly secure and simpler to implement, so you should do that.


Okay to use OpenSSL to encrypt then sign a message?

I see a few issues with this approach:

First, since you're signing the ciphertext and sending the signature in plain, anyone who has your public key can verify that you did, in fact, sign that message, even if they won't be able to actually decrypt it.  This may or may not be something you want.
More importantly, anyone who intercepts the message can strip your signature and substitute their own (or, if the protocol allows it, leave the message unsigned).
Further, if the symmetric cipher used to encrypt the actual message is malleable (as e.g. many common non-authenticating block cipher modes are, at least to some extent), the interceptor might also be able to modify the message before re-signing it, for example replacing an embedded copy of your name or public key with their own.

The obvious solution to these problems is to follow the advice in the article you linked to:

Combine (e.g. tar) the plaintext and the public key of the recipient.
Sign the combined plaintext and recipient's public key.
Combine (e.g. tar) the signature and the signed message.
Generate a random key and encrypt the combined message and signature with a symmetric cipher using that key.
Encrypt the random key with the recipient's public key.
Combine the encrypted message from step 4 and the encrypted key from step 5.

I've followed your example above in keeping the symmetric and asymmetric encryption steps (4 and 5) separate — I'm not familiar with the OpenSSL tools, but many public key crypto implementations provide a way to do both in one step, since it's the only practical way to encrypt large messages with asymmetric crypto.  Similarly, the signing step typically involves first hashing the message and then signing the hash, but I haven't explicitly separated those steps since you didn't either.

Ps. It would also be possible (and perhaps preferable) to use key encapsulation (KEM) in steps 4 and 5, if your crypto toolchain supports it.  Basically, instead of generating a random symmetric key and then encrypting it with the recipient's public key (which generally involves padding and other complex details), you generate a random chunk of data within the message space of the asymmetric cipher (e.g. a random number less than the modulus, for RSA), encrypt it using the plain "textbook" version of the asymmetric cipher (with no padding or other complications), and also hash it to obtain the key for the symmetric cipher.  The recipient then decrypts the random data with their private key and hashes it to obtain the symmetric key.  The advantage of KEM is mainly one of simplicity, though, so if you're already working with a toolchain that supports normal asymmetric encryption with padding, but not KEM, then it's probably not worth it.


Cryptography elements needed for a story

Though quantum computers fit the requirements, I'm not sure they are the best option. A general purpose quantum computer capable of attacking modern encryption (RSA, AES) would have serious ramifications on society. It's not only applicable to this one cipher you are breaking.
Does it have to be the superior computing resources which gives the good guys the edge? Because I can think of several plausible storylines where the edge comes from a bright idea.
Option 1: Information about the passphrase.
If the good guys learn something about how the passphrase used to derive the encryption key was chosen they could easily reduce the search space time from millennia to months. For example the passwords are always lines from a book where some of the words are replaced with the first letter. Or something else. One way to learn such a pattern is they crack some other password picked by the same person which was encrypted with weaker encryption. The hero recognizes the pattern in this other password hypothesizes it may be a common method of selecting passwords and starts a brute force dictionary attack on the reduced space.
Option 2: General Cryptanalytic improvement.
Our hero is a master cryptographer. And uses an unknown but plausible cryptanalytic attack on AES to greatly improve speed. This attack could have greatly reduced runtime and it could work on only a fraction of the keys. It could be discovered that a sizeable fraction of keys have some undesired property which makes a superior attack possible (which still requires great computational resources) and they are unsure if the key happens to be such a weak key, they are likely to be able to quantify their success probability in advance.
Option 3: Identifying a flaw in how the data was encrypted
Whoever encrypted the data may have messed up. And accidentally left an easier route to attack it. It could be something like applying error correction after compression before encryption (the flaw in GSM). Or something which more directly leads to an attack like keeping a simple hash of the password. The heroes find this flaw and launch a more efficient brute force based on it.
Option 4: Attack the message not the key
Out heroes don't try to crack the encryption at all. They utilize knowledge of message and compression system used. and find what possible messages would result in desired size. Though if it's only size it's only viable if we had a small collection of possible messages and the attack will be quick. There are attacks on voice for example where we use size and timing to decipher words and phrases without breaking the encryption.


is the functional signature result relies on f(x) or on x where x is a message and f is a function?

A signature $\sigma$ created by $\mathrm{FS.Sign}(f,\mathit{sk}_f, m)$ is a signature on the value $m^* = f(m)$.
You can see this because the verification algorithm just takes the signature $\sigma$ and the image $m^*$ as input and hence signature validity syntactically does not depend on $f$ or $m$.
You can see this in Definition 3.1.

This is not only a syntax thing, however. If the scheme fulfills the property of "function privacy" (Section 3.1), a signature on $m^*$ is required to look independent of the function and pre-image used to create it. With details omitted, the property requires the following: Given a signature on $m^* = f_0(m_0) = f_1(m_1)$, the verifier cannot tell whether the signature was created by $\mathrm{FS.Sign}(f_0,\mathit{sk}_{f_0}, m)$ or by $\mathrm{FS.Sign}(f_1,\mathit{sk}_{f_1}, m_1)$.

I hope I understood your question correctly.


Is RSA in a ECB-like-mode safe for bulk encryption?

Well, reusing a key isn't a problem; after all, RSA keys are generally used many times.

However, if you fix the padding, there does exist one other potential problem; message malleability.

To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$.  To send these, Alice actually sends:

$E(X_1), E(X_2)$

$E(Y_1), E(Y_2)$

Now, Eve can't modify each individual block (RSA with proper padding prevents that); what she can do is mix-and-match blocks, as so:

$E(X_1), E(Y_2)$

This would decrypt at $X_1, Y_2$, which might not be what Alice and Bob whats.

If you are silly enough to use RSA encryption in this manner, you do need something that binds the blocks together (or alternatively does some sort of integrity checking on the entire message).

As for whether people ever do this in practice, well, no they don't -- not because of security, but because it's so inefficient; using the RSA algorithm to communicate a symmetric key, and using that symmetric key to encrypt the message is far more efficient.


How to encrypt with elliptic curve cryptography (ECC)?

Why can't you encrypt a message with a public key generated via ECC?

Well, for starters, you need to realize that ECC is a collective term for a number of protocols that use elliptic curves to do cryptography.  Some of these protocols (ECIES, ECElGamal) are public key encryption methods (that is, they have a public encryption key, and the private decryption key, and the public encryption key allows you to encrypt a message, but not decrypt it); with these, you most certainly can encrypt with the public key.  Of course, there are other protocols (ECDH, ECDSA, EdDSA) which do other things, and are not intended to encrypt messages.

  How can two peers Alice and Bob agree on shared secret (symmetric key), both of which having elliptic-curve-based public-private key pairs?

Actually, yes, Diffie-Hellman translates nicely to elliptic curves, that version is called ECDH, and is widely used.  ECDH works mostly like classical DH (with the minor differences being mostly the validity checking that you need to do on the public shares)

  Could schemes be based on a plain Diffie-Helmann key exchange, where you use the other's public key as authentication (signing messages)?

It doesn't make sense to use a public key as 'authentication'; to make sure that the message came from you, you need to stir in something that not everyone knows.  This could be a private signature key, or it could be a secret shared between you and the intended recipient.  If it's something everyone knows, then everyone can produce that message, and so it wouldn't actually serve as 'authentication'


What is the padding scheme for the original Tiger hash?

For drop-in compatibility, we adopt the outer structure of the MD4 family: the message is padded by a single '1' bit followed by a string of '0's and finally the message length as a 64-bit word. The result is divided into n 512-bit blocks.

http://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/node2.html

I assume this 64 bit word is little endian, like the rest of Tiger and like the MD4 padding.

For reference the RFC1320 which describes MD4 says:

  a sequence of
     bytes can be interpreted as a sequence of 32-bit words, where each
     consecutive group of four bytes is interpreted as a word with the
     low-order (least significant) byte given first.

  [...]

  Step 1. Append Padding Bits

  The message is "padded" (extended) so that its length (in bits) is
     congruent to 448, modulo 512. That is, the message is extended so
     that it is just 64 bits shy of being a multiple of 512 bits long.
     Padding is always performed, even if the length of the message is
     already congruent to 448, modulo 512.

  Padding is performed as follows: a single "1" bit is appended to the
     message, and then "0" bits are appended so that the length in bits of
     the padded message becomes congruent to 448, modulo 512. In all, at
     least one bit and at most 512 bits are appended.

  Step 2. Append Length

  A 64-bit representation of b (the length of the message before the
     padding bits were added) is appended to the result of the previous
     step. In the unlikely event that b is greater than 2^64, then only
     the low-order 64 bits of b are used. (These bits are appended as two
     32-bit words and appended low-order word first in accordance with the
     previous conventions.)

  At this point the resulting message (after padding with bits and with
     b) has a length that is an exact multiple of 512 bits. Equivalently,
     this message has a length that is an exact multiple of 16 (32-bit)
     words. Let M[0 ... N-1] denote the words of the resulting message,
     where N is a multiple of 16.


How random is the shared secret in the Diffie Hellman key agreement

The shared secret generated by the Diffie–Hellman key exchange is a random element of the subgroup of the multiplicative group modulo $p$ generated by $g$.

In particular, for $g$ and $p$ chosen as specified in RFC 2631 section 2.2, i.e. so that $p = jq+1$, where $q$ and $p$ are both prime, $j$ is a small number (often 2, making $p$ as safe prime) and $g$ generates the order $q$ subgroup modulo $p$, this subgroup contains $q$ elements and the shared secret therefore (assuming that the private keys are appropriately generated, of course) has $\log_2 q$ bits of entropy.

The recommended way to extract this entropy into a useful form is to hash the shared secret or, better yet, feed it into a key derivation function like HKDF (RFC 5869).
What you're asking is how bad is it if we simply take the first (or last) 256 bits of the binary encoding of the shared secret and use them as an AES-256 key?

My answer, a bit surprisingly, would be "not too bad."  We may not get quite 256 bits of entropy out of the secret that way, but we ought to get at least 247 bits or so (assuming that the secret is long enough to have that many bits in the first place, of course), which is still plenty enough for any practical purposes.

Specifically, let's assume that $p$ is a safe prime (i.e. $j=2$), and that the secret is padded to the minimum number of bytes needed to encode $p$, as specified in RFC 2631.  Thus, the padded secret will be a bitstring with $n = 8 \cdot \lceil (\log_2 (p+1)) /8 \rceil \le \log_2 p + 8$ bits, and will contain $$m = \log_2 q = \log_2((p-1)/2) = \log_2(p-1)-1 \approx \log_2 p - 1$$ bits of entropy.  When we truncate the secret to 256 bits, we throw away some of this entropy, but at most only as many bits as we remove from the length.  Thus, the truncated secret will contain at least $m - (n - 256) = 256 - (n - m) \ge 256 - 9 = 247$ bits of entropy.

Now, in the code you refer to, the secret is apparently not padded to a fixed number of bytes, but rather has leading zero bytes removed.  However, at least assuming that $q \gg 2^{256}$, this still should not make much difference.  (In fact, in some cases it might even slightly increase the entropy left after truncation.)

To see why, let $k = 8 \cdot \lceil (\log_2(z+1))/8 \rceil$ be the number of bits needed to encode the secret $z$.  First, we'll observe that ${\rm Pr}[k < 256] = {\rm Pr}[z < 2^{256}] \le 2^{256} / q = 2^{256-\log_2 q}$.  For, say, $q > 2^{336}$, this probability is negligible (less than $2^{-80}$).  Thus, for large enough $q$, we may safely assume $k \ge 256$.

Now, for each possible length $k$, the secret $z$ lies in the interval $2^{k-8} \le z < 2^k$.  Using the same argument as above, we may show that, for any given $k$, $z$ must have at least $k - 9$ bits of entropy, and that truncating it to 256 bits must leave at least $256 - 9 = 247$ bits of entropy.  Since we'll have at least 247 bits of entropy regardless of $k$ (except in negligible cases), we'll have at least 247 bits of entropy overall.

(For $j > 2$, the constant $9$ above becomes $8 + \log_2 j$ instead, but that makes little difference unless $j$ is huge, which it normally shouldn't be.)

All that said, none of the above should be taken as an argument against using a proper KDF to convert Diffie–Hellman secrets into key material.  You definitely should do that, if only because a) the standards say so, b) it's still more secure and c) it provides other benefits such as salting.
Still, it does appear that simply using the raw truncated D–H shared secret as an encryption key may not be quite as bad as one might assume just based on reading the RFCs.


DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus

Yes, this is totally feasible. Unless $p$ is purposely chosen as a safe prime, there's a good chance that's easy.
Computing $a$ given $B$, $p$, and $C=B^a\bmod p$ is a Discrete Logarithm Problem in the multiplicative group modulo prime¹ $p$, of order $r=p-1$.
For any DLP problem, there is a generic attack of cost a few times $\sqrt r$ group operations, Pollard's rho. Not only is $2^{\approx45}$ multiplications modulo 90-bit $p$ feasible, but that can be efficiently distributed on independent machines, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999, following their article in proceedings of CCS 1994).
Also, there is the generic Pohlig-Hellman DLP method, which can help if $r$ is of known factorization.Here for we can factor the 89-bit $r/2$ in a breeze. The main DLP reduces to a few easier DLPs in groups of smaller prime order. These can be solved by Baby-step/Giant-step for small ones, or Pollard's rho and it's distributed variant for large ones. A typical factorization of $r$ has a largest prime factor $q$ of multiplicity 1 and much larger than other primes dividing $r$, so that the work is dominated by $\sqrt q$ group operations. Here, it is not told if $p$ was chosen such that $q=r/2$ is prime (which would make Pohlig-Hellman pointless), thus there is a fair chance that $q$ is sizably less than 89-bit, easing attack greatly.
There are even more efficient methods in the case of the multiplicative group $\mathbb Z_p^*$ that we target:

The index calculus algorithm. I'm not familiar with it, but would say it is likely the method of choice here if $(p-1)/2$ is prime.
The DLP variant of the General Number Field Sieve, which is the best known method for large $p$. The current GNFS DLP record is for a $795$-bit $p$ with $q=(p-1)/2$ prime (the hard case), see Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann's Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment, in proceedings of Crypto 2020.

¹ The question's mention of Diffie-Hellman key exchange suggests $p$ is prime. If not, we can factor $p$ into $\prod{p_i}^{\alpha_i}$, solve for $a_i$ the problems $B^{a_i}\equiv C\pmod{{p_i}^{\alpha_i}}$, then use the Chinese Remainder Theorem modulo the ${p_i}^{\alpha_i-1}\,(p_i-1)$ to find a solution $a$.


How to select parameters based on some condition

I'll first assume $\phi$ is known, which would be the situation in RSA at key selection.

A common method could be to select (odd) $\mu$ at random in some appropriate interval until $\gcd(\mu,\phi)=1$ is satisfied. In the context of RSA, it is fine (if we ignore performance an interoperability issues) to choose an RSA exponent at random in $[3\dots\phi-3]$ that is coprime with $\phi=(p−1)(q−1)$.

Another option would to restrict to prime $\mu$, which increases the odds that $\gcd(\mu,\phi)=1$: for random choice of large primes $p$ and $q$, a moderate prime $\mu$ has odds $({\mu-2\over\mu-1})^2$ to be acceptable. For example, $\mu=65537$ (the most common choice for RSA) would likely be fine.

When candidates for $\mu$ are examined in prescribed order, from the choice of $\mu$ a little information leaks about $\phi$; this is usually a non-issue.

If we somewhat must arrange that $\mu$ be chosen without knowledge of $\phi=(p-1)\cdot(q-1)$, one option is to select distinct primes $p$ and $q$ of some bit size $b$ such that $(p−1)/2$ and $(q−1)/2$ are primes; in this way, any odd $\mu$ less than $b-1$ bits verifies $\gcd(\mu,\phi)=1$.


Double Ratchet Algorithm - What if the receiving wants to send the second message before the initiator?

I read again and again and I figure out how.

According to this section:

  (This assumes Alice begins sending messages first, and Bob doesn't send messages until he has received one of Alice's messages. To allow Bob to send messages immediately after initialization Bob's sending chain key and Alice's receiving chain key could be initialized to a shared secret. For the sake of simplicity we won't consider this further.)

So, actually Bob's sending key chain and Alice's receiving key chain are initialized with a shared key. This allows Bob send the firsts messages of the Double Ratchet step (second+ messages).


Why would Carter-Wegman-style message authentication not be broken by P = NP?

While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth.

What they are talking about is a Carter-Wegman authentication method that uses a stream of random bits as a part of the process (just like a one time pad uses a stream of random bits to encrypt).

Normally, when we implement CW, we use some almost universal (au) hash function, and pair it up with some cryptographical object.  The au hash function processes the message being MACed; and then use the cryptographical object to disguise the au hash output.

How this works: using the au hash implies that someone who doesn't know the au hash key cannot generate two messages that have a nontrivial probability of hashing to the same value (and there are a number of constructions where this is provable).  However, someone who sees the au hash output can deduce rather a lot; hence we disguise the intermediate au hash to generate the full hash with the cryptographical object.

In a one-time-pad setting, one of the things we could do is replace the cryptographical object with "xor the au-hash with the next set of pad bits"; this also effectively disguises the hash output, and so satisfies the criteria (and an oracle that can do NP cannot recover the au-hash, because (just like the one-time pad), there's not enough information to do so).  Note: actually, in this construction, you'd need a delta almost universal hash function; if you care about those details, ask in a separate question.

On the other hand, those two wouldn't be quite the only things that would be left in the cryptography toolbox.  In addition, we have:

Secret Sharing (where if someone has fewer than the requisite number of shares, they literally don't have enough information to reconstruct the secret)
Some key distribution schemes (where someone issues key shares to parties, two parties can generate the same key, and no one else with fewer than k key shares (where k is a security parameter) have enough information to reconstruct their secret.


How does the round function in this particular Feistel cipher work?

It seems to me that the exercise is missing some context (which is presumably to be found in the textbook it's taken from).  Specifically, it defines a function $$f: \{0,1\}^4 \times \{0,1\}^4 \to \{0,1\}^4,$$ but does not explicitly state what role this function is supposed to play in the Feistel encryption process.

That said, the usual way to define a Feistel encryption round (as given e.g. on Wikipedia) is $$\begin{aligned} L_{i+1} &= R_i, \\ R_{i+1} &= L_i \oplus F(R_i, K_i), \end{aligned}$$ where $L_i$ and $R_i$ are the left and right halves of the input block to encryption round $i$, $K_i$ is the $i$-th round subkey, and $F$ is some nonlinear function.

Presumably, the function $f$ defined in the exercise corresponds to the nonlinear round function that I've denoted by $F$ above.  Thus, presumably, one of its arguments is supposed to be the round subkey, while the other one is one of the input half-blocks, just like you say.  However, what's not obvious from the given definition is which argument is supposed to be the subkey, or whether the other argument is supposed to be the left or the right half-block (since either convention can be used, and they're essentially equivalent).

Anyway, if the exercise comes with an answer sheet, it should be easy enough to verify this just by doing the encryption is each of the possible ways and comparing the results with the expected answer.  Even with the small block size, getting the right answer just by change from the wrong encryption process should be pretty unlikely.


To encrypt a message, in RSA or other encryption schemes, we convert (encode) the messages into bits/bytes arrays that are dependent on the scheme in an invertible way!
If you consider only the English letters, with $A=0,\ldots, Z=25$ then you can make the encoding of a sequence of letters $m_0,m_1,\ldots,m_t$ with
$$m = \sum_{i=0}^t 26^i \cdot m_i$$ This method is common way to encode, remember the binary encoding? A similar idea applied here, and note that the decoding is unique. Numbers are easily converted into octets (bytes) in a computer and usually byte array is processed, some schemes use words, too.
You are going to have some problems now or future;

You cannot have $m \geq n$ where $n$ is the RSA modulus. If your messages are longer than the RSA modulus, then you need to split your message into parts.
In your case, $p=11,q=13$ then $n = 143$. This can only encrypt one letter at a time. Use larger modulus, or encrypt one by one!.

We don't use RSA for encryption, we rather use it for signatures and for hybrid encryption like RSA-KEM.

RSA encryption needs proper padding like PKCS#1v.4 or OAEP to be secure against the attack, see Twenty Years of Attacks on the RSA Cryptosystem.

RSA Signing is Not RSA Decryption

For signature, one must use the Probabilistic Signature Scheme (PSS).

The padding, is not enough to be secure, one needs to have constant time implementation against the side-channel attacks.

To see how real RSA encodes see rfc8017


Why does Smart's attack only work on anomalous curves?

You can find an answer at section 5.4 of Washington's Elliptic Curves: Number Theory and Cryptography.

Following their notation (and skipping the technical details about reduction $\mod p$ and $E_r$ subgroups), let $N=\#E$ and assume $p\nmid N$. Let $\ell_1=\lambda_1(N\tilde P)$, $\ell_2=\lambda_1(N\tilde Q)$, so that $k\equiv \ell_2/\ell_1 \mod p$ (we want to prove this). Set also $\tilde K = k\tilde P-\tilde Q$. We have

$$k\ell_1 - \ell_2=\lambda_1(kN\tilde P-N\tilde Q)=\lambda_1(N\tilde K)\equiv N\lambda_1(\tilde K) \mod p.$$

In the last step you cannot continue, because the initial assumption makes $N$ invertible $\mod p$ and you can't say that this equals $0$, failing to prove that $k\equiv \ell_2/\ell_1 \mod p$. You can see that this proof does work if $p$ divides $N$.

To my understanding, this would mean that if $p$ divides the number of points, then you may also perform the attack, but I haven't read enough on it to confirm this.


Conditions for a successful Differential Power Analysis attack

Can a variable that is not explicitly computed correlate with the
  power consumption?

Yes, and this can happen in several ways. When you say "not computed explicitly", I assume you mean that the computation is performed on a masked value or share instead. That is, the secret inputs (referred to as the key by the paper you link to) themselves do not directly appear in any of the computations. Below, I discuss why this condition is not enough.
So "correlation" is used in a very broadway. In fact, for higher-order attacks nonlinear dependencies (i.e. not just linear correlation) can also be problematic.

First, let's consider a traditional boolean masking scheme: add a random mask to the secret input of your combinatorial circuit.
Let's say that you've implemented a very nice masking scheme: operations are never done directly on the unmasked (secret) values and leakage, in general, is carefully avoided. So you made sure to choose the operations with care so that no intermediate values depend on the unmasked values.

(Un)fortunately, it has been shown that hardware glitches can leak information anyway. This paper concludes that this is a general problem for non-linear masked gates:

  It has turned out that masked nonlinear gates, such as AND, NAND, OR
  and NOR gates are susceptible to DPA-attacks, while masked linear
  gates, such as XOR and XNOR gates, are resistant to DPA attacks.

The general idea is that the number of gates affected by a glitch depends on the unmasked input, for example this paper has a nice example of a masked AND gate.
Methods that solve this problem have been proposed since then, though (see below). This is an area of active research.

Higher-order attacks are another possibility. I won't go into detail here, but if information from several points in the implementation can be combined, this (i.e. higher-order statistical moments) may leak information about the unmasked data.

I think my recent answer about threshold implementations is worth mentioning here.
There, mutual information analysis (MIA) can be used to attack the proposed scheme. Hence, it's an example of how, even though each share of the realization is independent of at least one of the input shares, an unshared (secret) value may still be revealed using MIA. Of course, simply observing several shares (also a higher-order attack) would also work. Higher-order threshold implementations attempt to mitigate this problem (but currently don't entirely succeed).

Note: Some comments on the question have also mentioned the influence of memory access. As my knowledge of that subject is relatively limited, I'll leave the discussion to others. So you can take this answer to be mainly about the combinatorial part of an implementation.

The generation of random masks is also an interesting subject by itself, and much could be said about that.
Other types of side-channel attacks, such as fault-attacks, will also lead to several other difficulties. For example, a fault-attack model allows active disruption of the implementation (injecting faults) which may lead to other ways of revealing key bits which do not explicitly occur in any computation. Consider what happens if you sabotage the RNG that provides the masks.


Challenge Response Authentication - Client Generating Challenge

The attacker can use replay attack, i.e, he/she can replay a challenge that is signed by the user in the past(which is used as a challenge to server) and can send this as a nonce to the server. To avoid this, server generates and sends the challenge.The idea works if server maintains a list of previous nonce used but this has its limitations on practical implementation.

Hope this helps.


Schnorr Identification protocol sometimes wrong?

Good that we have resolved the issue (the bug is to compute $g=h^{(p-1)/q} \bmod p$ instead of $g=h^{(p-1)/q} \bmod q$).

When implementing such protocols you can take the following "rule of the thumb":

When working with group elements of the multiplicative group $\mathbb{Z}_p^*$, i.e., performing group operations, then you always do your computations modulo $p$, e.g., you compute $z=y w \bmod p$.
When working "in the exponent" and your "base element" ($g$ in that case) generates a subgroup of order $q$, then you perform the computations on these integers modulo $q$, i.e., you compute $s=cx+e \bmod q$ (Note that when you then take your group element $g$ to the power of $s$, then you do another group operation, i.e., compute $g^s \bmod p$).