TLS: Is Integrity assured when using NULL cipher

To answer your main question.
Yes, NULL ciphersuites do provide authenticity and integrity checks but not confidentiality for the TLS traffic.

There is still a specified key exchange algorithm (e.g. RSA) for the TLS handshake protocol. The client will generate a pre-master secret and encrypt it with the server's public key for server authentication.
The session key is then derived and the MAC keys are generated from it. Authentication of messages is provided by demostrating knowledge of the MAC keys.

However, the toolkit Openssl warns that NULL ciphersuites offer no encryption at all and are a security risk. They are disabled unless explicitly included.

RFC 4785 classifies them as authentication-only ciphersuites (with no encryption).
Not sure about the your other question.


One trivial possibility is to sets $m=2^n$, and defines $f(x)$ as the $m$-bit vector $y$ with
$$y_j=\begin{cases}
1&\text{if }j=\displaystyle\sum_{i=0}^{n-1}x_i\,2^i\\
0&\text{otherwise}
\end{cases}$$
where subscripts denote bit index.

Is that "succinct"? I can't tell for lack of a definition. We sure can make an $O(n)$ representation of $y$; in essence, $x$ will do!

If there was not the restriction $|S|<n$, we could take $S=\mathbb{F}^n_2$, with $|S|=2^n$, thus there would no solution with $m<2^n$.

Kodlu's answer is about making use of $|S|<n$ in order to minimize $m$, using coding theory. Also it shows there can be cryptographic applications.


As a cryptographic primitive, what does a nonce provide?

A nonce is not a cryptographic primitive. Cryptographic primitives are algorithms that are part of a cryptographic scheme. For instance, a block cipher can be a cryptographic primitive in a block cipher mode of operation. AES is a primitive in AES-GCM. Nonces are numbers-used-once; they are just a description of unique integer values (usually with a specific encoding in bytes).

AES as a block cipher is not cryptographically secure as a generic cipher (this may surprise you). The reason for this is that once the key is reused with the block cipher it will output the same value for the same input. To be IND_CPA secure the cipher should not output any indication about the plaintext, and outputting the same value clearly indicates that the same plaintext was used.

For this a block cipher mode-of-operation can be used. Some modes of operation such as CBC require input indistinguishable from random. CTR and many modes derived from it such as AES-GCM however just require a nonce. So this is - among possibly other uses in other schemes - what a nonce provides: it makes sure that a mode-of-operation is secure even if the same key is used.

In general a nonce is used in cryptography to provide uniqueness within a function even when the other inputs remain identical.


Password hashing security of argon2 versus bcrypt/PBKDF2?

Coming up with a specific number is hard. Realistically, all three options take you well out of the realm of ever having more than the absolute worst passwords brute-forced by an attacker.
The primary gain of scrypt and Argon2 over bcrypt is a hit to parallelism due to the addition of memory requirements. GPUs with thousands of cores will need (but don't have) absurd amounts of memory, so most of those cores will need to remain idle. FPGAs and ASICs become much more expensive as they have to incorporate large amounts of memory, so you're really just forcing an attacker to trade a significantly larger number of dollars for equivalent parallelism.
The primary gains of Argon2 over scrypt (anyone correct me if I'm wrong):

improved resistance against Time Memory Trade-Off Attacks (TMTO),
better side-channel resistance (scrypt is vulnerable to cache-timing attacks due to secret-dependent memory access patterns), and
the ability to increase CPU and memory requirements independently of one another.


Examples of modern, widely used ciphers that suddenly fell?

This question is quite broad by specifying a sudden fall to cryptanalysis and therefore my answer might not be as complete as you wish it to be.

If by "become practically attackable, or close enough that use is strongly discouraged" you imply not an academic breach but assume a weaker attacker such as a single ciphertext attack, then there are quite a few ciphers that satisfies this condition. Under this assumption, modern block-ciphers are mainly vulnerable to brute force attack. Should the key length of DES be longer so we would not be able to do an exhaustive search then it would still retain a certain level of security (while its use still be strongly discouraged).

Moving to strongly used block ciphers, here are a few that have been academically broken or weakened to be considered as insecure.

FEAL (Block Cipher)

The first block-cipher that came to my mind with such characteristic is FEAL. It was design in 1987 and aimed to replace the DES by providing fast encryption capacities for 8-bit platforms. It was not widely used and (un)fortunately it was broken even before becoming a new standard in 1990.

Should you teach or would like to practice cryptanalysis, I would recommend breaking FEAL-4 (as 4 rounds) or FEAL-8. It is a great learning exercise.

Some resources :

Differential Cryptanalysis for dummies by Jon King
Differential Cryptanalysis of Feal and N-hash by Eli Biham and Adi Shamir

DES (Block Cipher)

DES is another example. Broken by differential cryptanalysis in 1990 by Eli Biham and Adi Shamir.

  In this paper we develop a new type of cryptanalytic attack which can break the reduced variant of DES with 8 rounds in a few minutes on a PC and can break any reduced variant of DES (with up to 15 rounds) in less than $2^{56}$ operations.

from their paper : Differential Cryptanalysis of DES-like Cryptosystems. I really recommend reading this article or at least the extended abstract.

Remark: To break the 16 rounds, one would need $2^{57}$ pairs. The number of cipher texts needed is twice the number of pairs.
On these pairs, only $2^5$ would be used (excluding the wrong pairs that can be easily discarded during the collection phase). Using 15 different characteristics with a probability of $2^{-56}$, 18 bits of the key could be found. Therefore this attack involves slightly more work than a brute-force attack. (Thx Jerry for pointing this out).

3 years later, Mitsuru Matsui introduced a new method to break DES.

  As a result it is possible to break a 8-round DES cipher with $2^{21}$ known-plaintexts and 16-round DES cipher with $2^{47}$ known-plaintexts, respectively. Moreover this method is applicable to an only-ciphertext attack in certain situations

from his paper: Linear Cryptanalysis Method for DES Cipher (another good reading).

A5/1 (Stream cipher)

Moving to stream cipher we have A5/1 which is responsible of the privacy of the communication between GSM and the antenna. Developed in 1987, with a key length of $64$ bits. In 1997, Golic presented an attack based on solving sets of linear equations which has a time complexity of $2^{40.16}$.
In 2000 Eli Biham and Orr Dunkelman  published an attack with a total work complexity of $2^{39.91}$ A5/1 clockings given $2^{20.8}$ bits of known plaintext. The attack requires 32 GB of data storage after a precomputation stage of $2^{38}$.
Remark: while A5/1 is completely broken (cf Snowden leaked files) it is still in use in our cell phones...

Some resources:

Real Time Cryptanalysis of A5/1 on a PC by Biryukov, Shamir and Wagner
A Real-World Attack Breaking A5/1 within Hours by Gendrullis, Novotný and Rupp (2008)
A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony by Dunkelman, Keller, and Shamir (2010)

RC4 (Stream cipher)

RC4 (as Rivest Cipher 4) is a stream cipher mainly used in SSL (1995), TLS (1999), WEP (1997) and WPA (2003/2004). It was designed in 1987 but the code was unknown until being leaked in September 1994 (security by obscurity, here I am...)

Some resources:

Weaknesses in the Key Scheduling Algorithm of RC4 by Fluhrer, Mantin and Shamir (2001)
Full Plaintext Recovery Attack on Broadcast RC4 by Isobe, Ohigashi, Watanabe, and Morii (2013)

MD5 (hash function)

Infamous hash function, designed in 1991. Five years later, Dobbertin announced a collision of the compression function of MD5.
In 2009, the complexity of the attack was in  $2^{39}$ (initial pre-image complexity is $2^{128}$.

SHA-0 (hash function)

Published in 1993, revised a few years later due to a significant flaw as SHA-1.
At CRYPTO 98, a first collision was found in $2^{61}$ (initial complexity in $2^{80}$.
In February 2005, an attack by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu was announced which could find collisions in SHA-0 in $2^{39}$ operations. Another attack in 2008 applying the boomerang attack brought the complexity of finding collisions down to $2^{33.6}$.

SHA-1 (hash function)

Published in 1995 as a revision of SHA-0 (see above), it has been first weakened with attacks of complexities:

$2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
$2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
$2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).
$2^{57.5}$ call of the compression function, per Marc Stevens, Pierre Karpman and Thomas Peyrin:  Freestart collision for full SHA-1, 2015.
Until finally The first collision for full SHA-1 was found by Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov and published at CRYPTO 2017 (Best Paper Award) with $2^{63}$ calls to the compression function.

I'm probably missing a lot of other block ciphers, but these are the ones mainly known to my knowledge.


What makes lattice-based cryptography quantum-resistant?

The attacks on RSA and Elliptic curve cryptography(ECC) are based on Shor's quantum algorithm which is used for integer factorization in the context of RSA.

Correction: Note that, as pointed out by @yyyyyyy in the comments, Shor's algorithm for DLP does not factor; neither is it based on finding the order of an element (which is usually known anyway in a DLP context). Both variants have in common that Shor finds the period lattice of a certain map, and while in the factoring context this period is indeed (the $\mathbb{Z}$-multiples of) the order of an element, the lattice is two-dimensional in the discrete-logarithm setting (and contains a vector of the form $(,−1)$ where $$ is the solution to the DLP instance).

Cyclic groups are at the heart of RSA (over integer rings) and ECC (over additive groups defined on an elliptic curve over finite fields), thus the vulnerability.

However, lattice based crypto does not rely on such structures. Neither do code-based cryptosystems (McEliece, for example) so they are resistant to known quantum attacks.


Rationale for verification with cofactor $2^c$ in EdDSA?

It's flawed to imagine that "more stringent" is somehow stronger.  Actually ed25519-dalek's verify_strict method makes this mistake.
There are many plausible verification methods, which all define valid signature schemes based upon the same ed25519 keypairs.  You'll find them described in https://eprint.iacr.org/2020/1244 and https://hdevalence.ca/blog/2020-10-04-its-25519am
Almost none of those schemes agree perfectly with batched ed25519 signature verification however because batch verification randomly cancels out some cofactor tweaks.
If you employ ed25519 in a consensus protocol, like for accounts on a blockchain, then you'll want batched ed25519 verification that agrees perfectly with single ed25519 verification.  In such cases, you should use ZCash's ed25519 crate ed25519-zebra.  Afaik, all other ed25519 implementations exhibit variations between batched and single verification (as of march 2021).
I doubt TLS would adopt cofactor clearing verification, in part because cofactor-less verification runs slightly faster than cofactor clearing verification.  In fact, TLS could already batch verify ed25519 because one never has third parties check TLS handshakes in consensus protocols.  I suppose a CA could issue a certificate that worked only intermittently and only on some clients.


As classical Yao circuit, two-party have their own input independently, why he assumes that they both know neither input?

Consider the circuit $(a_1 \oplus b_1) \land (a_2 \oplus b_2)$ where Alice's input is $a_1,a_2$ and Bob's input is $b_1,b_2$. The bits going into the AND gate are not known to either party, so you can't use one of the half-AND constructions.

Parties know their inputs to the circuit but not the input to every gate in the circuit. The bits going into an internal gate in the circuit can be influenced by both parties' inputs, so that neither knows the value in the clear. (You can indeed replace AND gates with half-AND gates at the input layer of a circuit.)


To obtain the tag, OCB xors the plaintext blocks and encrypts them. Thus a sufficient condition for a forgery is finding another plaintext with the same xor as an existing plaintext.

Consider a known plaintext attack where the attacker obtained (plaintext, ciphertext) pairs for two messages encrypted using the same key and nonce. The attacker picks between the two known blocks at each position, attempting to produce the same xor of the plaintexts.

This leads to a system of 128 linear equations, one equation for each bit in the tag. These equation constrain the attackers choice of blocks. If the messages are long enough so that the system of equations isn't overdetermined, they can solve that system of equations efficiently via standard linear algebra. If the plaintext were linearly independent, messages 128 blocks in length would suffice. In practice they're not, so you need more blocks, but I expect that increase to be modest.


Pseudorandom number generator for which it is impossible to deduce the seed

Random number generation is the generation of a sequence of numbers or
  symbols that cannot be reasonably predicted better than by a random
  chance... Source: Wikipedia

It follows that "an attacker [with] all or part" of the sequence cannot "predict any non-given [part of the sequence] better than guessing," as hinted in a comment, so guessing is the best an adversary can do.

The original question mentions pseudorandom data and an original seed, without relation to RNGs, so perhaps the question is missing something and I'm answering the wrong question.


Something like this (for AES)? If this is the kind of thing that you are looking for then I will expand it to include other ciphers, attributes, and hash algorithms.

--------------------------------------------------------
Symmetric Ciphers | Mode | IV Needed | Authenticated |
------------------+------+-----------+---------------+--
       AES        | CBC  |    yes    |      no       |
       AES        | CTR  |    yes    |      no       |
       AES        | CFB  |    yes    |      no       |
       AES        | OFB  |    yes    |      no       |
       AES        | ECB  |    no     |      no       |
       AES        | CCM  |    yes    |      yes      |
       AES        | GCM  |    yes    |      yes      |
       AES        | XTS  |    yes    |      no       |
       AES        | OCB  |    yes    |      yes      |
------------------+------------------+---------------+--


One key difference between cryptographic hash functions and PRGs is this:

Pseudorandom generators (PRGs) are secret key algorithms.  A PRG's user needs to provide it with some random input that must be kept secret from any adversary.  If there is no such input or it's not secret, the adversary can predict the output.
Cryptographic hash functions are (usually) unkeyed algorithms.  They are designed to work in certain scenarios where there is no secret information at all.  It should be hard for example for an adversary to find any input that produces some known output (preimage resistance), or a second input that produces the same output as a known input (second preimage resistance).

If you can grasp this and its implications for your topic you will be well ahead. A key observation is that blockchain is a public ledger.


What is the public key and signature sizes for XMSS?

The original XMSS paper (eprint 2011/484) discusses an older version of XMSS, which does use rather larger public keys (and I suspect they got the signature size slightly wrong - they forget the idx_sig part of the signature which specifies which WOTS+ leaf they're using).

The XMSS RFC defines a newer version, with considerably smaller public keys (and slightly larger signatures).  The more recent XMSS/LMS comparison paper which you cited (eprint 2017/349) uses the RFC version of XMSS for the comparison.

I believe that the version defined in the RFC is what people generally use, and so the values in the comparison paper are the ones which are accurate.

As for the differences between the original version of XMSS and the RFC, well,
here's the main difference: in the original paper used masks stored in the public keys to provide randomization; the problem with this is, because they use the same masks in different parts of the Merkle tree, this opens them up to multitarget preimage attacks.  In the RFC version, they compute the masks dynamically (and hence they don't need to be in the public key). Because each mask is now different, multitarget preimage attacks don't apply (at the cost of the computation needed to generate the masks dynamically).

A more minor difference is that the RFC version includes a randomizer 'r' in with the signature (which is hashed along with the message); making this randomizer be unpredictable means that we don't depend on the collision resistance of the hash function (given that we rely on preimage or second preimage resistance everywhere else, this is a win).


Goofs that could creep in ECDSA signature verification?

Checks for $r$ and $s$

You should perform checking on $r$ and $s$ inside your signature verificatioin function. To be more specific you should check that $r$ and $s$ are integers in the interval $[1, n-1]$ as there are known attacks on related ElGamal signature schemes that do not have this check included. This could be a plausible attack on ECDSA if you do not check that $r \neq 0$ (or more generally, $r\not\equiv0 \pmod n$):

Suppose that $A$ is using an elliptic curve $y^2=x^3+ax+b$ over a field $\mathbb{F}_p$, where $b$ is a quadratic residue modulo $p$, and suppose that $A$ is using a base point $G = (0, \sqrt{b})$ of prime order $n$. This might be plausible as some entities might want to select a base point with $0$ $x$-coordinate in order to minimize the size of domain parameters. The adversary can now forge $A$'s signature on any message $m$ of its choice by computing $e=\mathrm{hash}(m)$. You can easily check that $(r=0, s=e)$ is a valid signature for any $m$.

Reduction mod $n$ after reduction mod $p$

During ECDSA signature verification you will have to compute $R=u_1G + u_2Q$. Your elliptic curve operations might be implemented in a way that the multiplication and / or addition will automatically perform a reduction$\mod p$ (order of the prime field). Note however, that you have to reduce the $x$-coordinate again, this time$\mod n$ (order of the generator). For me (and for the testvectors I had used), verification always worked without the reduction$\mod n$, which in my opinion, is the dangerous thing here. There might be curves / testvectors for which verification would fail without this last reduction step. I will implement some more curves (atm I had only used brainpool curves) and will post an update about this.


Can the SHA256 hashes of consecutive integers be attacked?

If we assume that the range of possible values of $n/k$ is sufficiently large that it is infeasible for the attacker to scan through $\operatorname{SHA256}(ik)$ values (and look for a match in one of the hashes), then it would appear to be secure.  There is no known weakness in SHA256 about hashing related messages.


What is base of $\log$ in Subexponential Algo for DLP?

In this case, the base does not matter as the $\log$ terms are wrapped in an $O$ expression. The $O$ expression lets you throw away constant factors and to convert something base $X$ to base $Y$ is simply $\log_X Z = \frac{\log_Y Z}{\log_Y X}$, well, $\log_Y X$ is a constant, so it can be thrown out in the $O$ expression.

The reason the second reference explicitly use $\ln$ is that the $O$ expression includes an exponent that does not also contain an $O$ expression. In this case, the base does matter.


As far as I know, there are many libraries that use lattices and LWE schemes to implement fully homomorphic Encryptions.

This is a set, Most of them is in C++ and Only one by MSFT is C#, But in all cases you can port the code to python aftor compiling:

HElib in C++
SEAL By MicroSoft C++/C#
Palisade C++
FHEW C/C++
TFHE C++
NFLib C++

Note: The set in no particular order.


Can we use a hash-based stream cipher against DPA attacks?

There seems to be not many effective DPA attacks against SHA

How do you come to that conclusion?  Is it because there aren't many published results of using DPA attacks against SHA?  Well, that's mostly because SHA is most often used to hash publicly available data, and so there's less of a point using a DPA attack to recover that data.

Now, any side channel attack (such as DPA) is actually an attack against the implementation, not against the base crypto.  Of course, if we consider DPA attacks against SHA implementations, we need to consider "how difficult is it to make a SHA implementation that is strong against DPA attacks?"

Well, there's nothing in the SHA architecture (either SHA-1, SHA-2 or SHA-3) that makes it specifically easy to provide such protection.  Now, you could create such an implementation (using, say, thresholding to disguise the individual bits); however that's likely to be significantly slower than a standard implementation.


The number of consecutive plaintext-ciphertext pairs $(x_i,y_i)$ of bits necessary is 256 if we know the LFSR taps (equivalently: the reduction polynomial) in advance, for the reason explained in the question. 512 is when we do not, because it creates more unknowns: the coefficients of the polynomial, in addition to the initial state.

If we know the LFSR taps, the initial state is all that's unknown, and is directly given by the vector of the first 256 values of $x_i\oplus y_i$ for an LFSR in Fibonnaci form (within a reflection, depending on notation). In Galois form, one option to find the initial state is to solve a system of equations.

If the LFSR taps are unknown, a standard algorithm is Berlekamp-Massey, which reconstructs the shortest LFSR state and feedback polynomial matching a given sequence of $x_i\oplus y_i$ (without taking the degree as input).

PS: I found the solution floating online, and adapted my notation to that. It is assumed that the feedback polynomial is initially unknown (or equivalently part of the key), hence the 512 pairs. The resolution is not explicitly per Berlekamp-Massey. Rather

With the LFSR in Fibonnaci form, the first 256 $x_i\oplus y_i$ give the initial internal state. The only remaining unknowns are the 256 coefficients $p_i$ of the feedback polynomial.
These 256 remaining unknowns are found by solving a system of 256 equations with 256 unknowns, built using the 512 $x_i\oplus y_i$. That system states that the internal state evolves from the first 256 $x_i\oplus y_i$ to the next 256 $x_i\oplus y_i$ after 256 steps with the reduction polynomial defined by the $p_i$.


Generating secure short activation code for offline applications

Let's examine the propositions in the question:

I thought of using the ISO 7064 Mod 97,10 formula
That provides no cryptographic protection against determined adversaries. ISO/IEC 7064 merely

  specifies a set of check character systems capable of protecting strings against errors which occur when people copy or type data.

I can generate the code using the above formula and use RSA with digital certificate. However, the output will be too long correct?
Yes. RSA signatures are at minimum roughly the width of the public modulus, that is for modern security 2048-bit or $2048\log2/\log10\approx617$ decimal characters. That's way too much to key in.
Besides, this means that the central authority has to have access to public keys of all hardware systems.
No. Verification of an RSA signature requires the public key of the authority entitled to produce it. Ignoring the size problem, there would be need for a single public/private key pair, with the private key held by the signing authority, and the same public key in all devices. Devices can recognize their serial number in the signed data.

While there are signature systems more compact than RSA, all yield a signature at least 10 times above the target "7-8 digits". Thus we can't use public-key cryptography.

The standard option there will be symmetric cryptography, with a secret key in each device. Standard practice is that the device key is derived from a master key known by the issuing authority, and the device's serial number, by some key derivation function (the Smart Card industry does this since the 1980s, under the name diversification). A single master key has to be kept, yet extraction of a device's key does not compromise the others. HMAC-SHA-256 would be a suitable derivation method. $\mathsf{DeviceKey}=\operatorname{HMAC}(\mathsf{MasterKey},\mathsf{SerialNumber})$ will do.

The unlock code can be some kind of Message Authentication Code of an index incremented at each reload and held in permanent memory by the device (and the authority's emission system), and truncated. That could be the decimal expression of $\mathsf{UnlockCode}=\operatorname{HMAC}(\mathsf{DeviceKey},\mathsf{Index})\bmod10^8$.

Normal operation is that the authority gets payment, finds $\mathsf{Index}$ for the $\mathsf{SerialNumber}$ in its database, computes $\mathsf{DeviceKey}$ then $\mathsf{UnlockCode}$, increment the $\mathsf{Index}$ for this device in the database. The device checks what's keyed-in against the $\mathsf{UnlockCode}$, and if there's a match activates and increment its $\mathsf{Index}$ in permanent memory.

Some issues need to be addressed:

The $\mathsf{MasterKey}$ and the $\mathsf{DeviceKey}$s are sensitive targets, and that might be vulnerable at the authority and manufacturing site. A HSM or Smart Card might help. In particular, a Smart Card good for a limited number of $\mathsf{UnlockCode}$s could be what clerks at the authority really use.
There should be significant redundancy in $\mathsf{SerialNumber}$ or whatever identifies devices in order to avoid clerical errors at the authority; ISO 7064 might be adequate there.
There is a risk that an attacker tries codes at random to unlock a device, perhaps automatically. A countermeasure is a delay between entries, perhaps increasing after a number of consecutive errors. It is also possible that there are two codes, a short one with a limit of 3 tries (6 digits will be fine), and a long one (say 12 digits) used as backup (similar to the PIN in a mobile phone SIM, with the PUK as backup).
The device should have appropriate mitigation for a variety of threats: unauthorized use with bypass of the payment, $\mathsf{DeviceKey}$ extraction, setting $\mathsf{DeviceKey}$ to a known value, setting $\mathsf{Index}$ to earlier value allowing reuse of an earlier code, resetting the aforementioned delay between entries by battery removal or other upset, side channel.. A classical goof is comparing the code keyed-in to $\mathsf{UnlockCode}$ using strcmp or similar library/language feature that leaks the position of the first mismatch by timing, which might be observable without opening the box, e.g. thanks to a LED or the keyboard scan EMI, allowing to find an 8-digit code in about 40 tries rather than 50 millions. Security engineering is not easy!
Users will loose or temporarily misplace codes, and rather than bother asking for a duplicate, will pay for a new one. The device should thus accept a few codes ahead. And then it's desirable to accept slightly out-of-order codes; that complicates the algorithm, especially for short codes (since all codes in the acceptable window need to be distinct). A simple option if a window of $w$ codes must be accepted is that $\mathsf{UnlockCode}=w(\operatorname{HMAC}(\mathsf{DeviceKey},\mathsf{Index})\bmod\lfloor10^8/w\rfloor)+(\mathsf{Index}\bmod w)$.
More generally it is possible to encode ancillary information within the code (e.g. reload amount). While we are at that, the length of the code can be variable, perhaps larger by one or two extra digits for high-value codes, for higher security.

Note: I do not see that Format Preserving Encryption really helps here, even when there is ancillary information to convey, since confidentiality of that seems to be more of a nuisance than a useful feature.


You're right that a key is not the same as a password. But a password can be used to derive a key. So some people just call the password a PSK, since it is pre-shared and is all one needs to know to derive an actual key.

In the case of WPA2-PSK, the password is indeed used to derive a key (using PBKDF, a slow hashing function). We call this key the Pairwise Master Key (PMK). Neither the password or the PMK are ever sent to the router. Instead, a four way handshake is used to ensure that the router knows that you know the PMK, and that you know that the router knows the PMK (i.e. a hacker didn't set up a fake router).

This handshake also allows both parties to derive another key, the Pairwise Transient key (PTK). This key is used to actually encrypt the connection.

So basically, no information that a hacker can use is sent over the connection. It only works if you and the router had the same initial password.

This also answers your second question. The PTK is different for every client, since it is based on the client's MAC address and some arbitrary numbers (nonces) sent in the handshake. As a result the PTKs are different for every client.

However, someone who knows the password (and therefore the PMK), and monitors the handshake (i.e. knows the MAC addresses and nonces) has enough information to reconstruct the PTK for another user. So it is possible to decrypt WPA2-PSK traffic provided you know the password.


Space needed to store an RSA private key

What's the size of a 4096 bit private key?

It depends.

The range goes from 512 bytes (only $d$, no formatting, no encoding) up to 5632 (full parameter set, maximal $e$ size, no formatting, hexadecimal encoding) bytes for two-prime RSA. If you also consider multi-prime RSA, the range is much wider.

So what influences the size of the stored private key then?

How do you encode the stored data?

No encoding, this will give no increase in storage need
Base64 encoding, this encodes 3 bytes of data into 4 bytes of encoded data
Hexadecimal encoding, this will encode 1 byte of data into 2 bytes of encoded data

How do yo format your data?

No formatting, this also means no overhead
ASN.1, this will give some overhead to make the structures parseable and the overhead will increase if you use XER instead of DER, the relevant standard is PKCS#1 (PDF) here as well as PKCS#8 for containers and PKCS#12 (PDF via Archive.org) as additional wrapper.
PEM, this will give you some overhead for internal structure and the header and footer of the data block

How much data are you storing?

The absolute minimum $p$, which will allow you to factor $n$ using simple division and will allow you to later derive $d$ "the usual way". This approach provides optimal storage requriments, assuming you're not willing to run the algorithms from 3. which would reduce the need for stored bits of $p$.
Only the private exponent $d$, which will give you a good storage characteristic, but also requires external supply of the public modulus $n$ and the public exponent $e$ for proper operation
A complete minimalistic approach $(n,p',e)$, this will require you to store $e$, but you can optimize it by hard-coding it as $F_4$. The technique is to store only a minimalistic amount of information of $p$, but enough to recover $p,q$ as per "On Factoring Arbitrary Integers with Known Bits" by Herrman and May (PDF) and "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities" by Coppersmith (PDF) . This reduces the storage requirement to 5120 bits, however I do no recommend this as it is highly non-standard and will give you large interoperability problems for a marginal storage saving.
The smallest (trivial) complete set $(p,q,e)$ which will allow you to recover $n$ using standard multiplication and will allow you to recover $d$ the usual way.
A middle-ground minimum $(n,d)$, this will not allow you to factor $n$ without external supply of $e$ (which may be an agreed-upon constant), but is enough to decrypt messages "classically"
Only the bare minimum $(n,e,d)$, this will allow you factor $n$ somewhat quickly if needed and it will allow you to do all operations without external data supply
A middle ground amount of data $(n,e,d,p,q)$, this will take away the "heavy" step of factoring $n$ but still leaves some computations to be done if you want that speed-up from the CRT.
The full set $(n,e,d,p,q,d_p,d_q,q_{\text{inv}})$, this allows you to load the data and outright start with the computations, including the CRT speed-up

  How does it compare to the public key?

Look at the above list of influencial factors and adapt the third major point, a public key "only" has the option $(n,e)$ there, meaning it can be larger than the private key or it can be significantly smaller, if you include the associated data in the private key.


3-round DES: what bit do we find? (Regarding matsui's Paper on Linear Cryptanalysis of DES)

The equation in (8) is obtained by summing (6) and (7), and is an approximation for the bit
$$
K_1[22]\oplus K_3[22].
$$
The sum of two key bits is still a bit.


Using Permutation polynomial to compute a MAC

It is clear that if $r_i$ is picked randomly the above Mac [defined in the second paragraph] would be secure.

Actually, that's not at all clear.  I would claim that if I were given that values of $Mac_i(a)$ and $Mac_i(b)$, I could compute the value of $Mac_i(x)$ for any $x$, as long as $a-b$ is relatively prime to $p-1$.  To do this, I need the value of $p$, $a$ and $b$, but not $k$, $r_i$, or for that matter, $g$.

To do this, I would compute $X = Mac_i(a) / Mac_i(b) \bmod p$; that value is $X = PRF(k,i) \cdot g^{a \cdot r_i} / PRF(k,i) \cdot g^{b \cdot r_i} = (g^r_i)^{a-b}$

I then compute $X^{(a-b)^{-1}}$, giving me the value $Y = g^r_i$.

I then compute $Z = Mac_i(a) / Y^a = PRF(k,i) \cdot g^{a \cdot r_i} / g^{r_i \cdot a} = PRF(k,i)$

Once I've done that, I can compute the $Mac_i$ of an arbitrary value $Mac_i(x) = Z \cdot Y^x = PRF(k,i) \cdot g^{r_i \cdot x}$


How is overflow handled in word addition steps in Salsa20?

Per the Salsa20 page -

  Each modification involves xor'ing into one word a rotated version of the sum of two other words modulo 232.

Adding two uint32s and ignoring the carry / overflow is equivalent to performing addition modulo 232.


calculate ESS IV initialization vector for aes- bc essiv encryption

Wikipedia has this documented.

Essentially: Let $\text{SN}$ by the current sector number encoded as a 128-bit integer. Let $K$ be the key used for encryption. Let $\operatorname{hash}(\cdot)$ be a hash function, which is specified in the cipher name.

Now the $\text{IV}$ is computed as $\operatorname{IV}(\text{SN})=E_{\operatorname{hash}(K)}(\text{SN})$.

The relevant code can be found for the key-calculation and for the actual IV.


CPA security of a stateless and deterministic encryption system

Here is the answer for why a deterministic public-key encryption scheme cannot be CPA secure.

For CPA security it is sufficient if an adversary can distinguish between encryptions of two messages $m_0$ and $m_1$. That is, an adversary gets to see an encryption $c \gets \textsf{Enc}(pk,m_b)$ for a random bit $b$ together with the public key $pk$. Now in order to figure out if $c$ is an encryption of $m_0$ all the adversary has to do is to recompute $\textsf{Enc}(pk,m_0)$ and check whether or not this value matches the given ciphertext thus breaking CPA security.


What does it mean in layman's term when it states that - "An algorithm running for polynomial time can break the scheme with probability p"?

The statement

  An adversary algorithm runs for $n^3$ time and can break the scheme with probability 0.001

can't be much simplified while keeping its meaning; nor can it be used to derive something useful for what happens after the algorithm is run 1000 times, beyond that this breaks the scheme with probability at least $1/1000$.

This statement is shorthand for: There exists some deterministic algorithm, designated/modeling an adversary, which when run with inputs(s) varying uniformly randomly across experiments, after running for $n^3$ time in each experiment, will break the scheme for a proportion at least $1/1000$ of the possible input combinations (in practice, if the number of input combinations is huge, for a proportion not significantly lower than $1/1000$ of experiments when enough experiments are run that the algorithm succeeds a significant number of times). Importantly: the varying inputs(s) of the algorithm might be from the problem to solve, or/and from a random source used by a randomized algorithm turned deterministic by moving its source of randomness as an input; that's left unstated.

It is not possible to conclude that $1000$ executions of the algorithm will break the scheme with odds better than $1/1000$; much less with certainty.

If the algorithm is purely deterministic, that is succeeds or fails depending only on inputs part of the problem to solve, repeating the experiment with the same inputs won't help at all, and odds of success are the same for 1 or 1000 runs: (at least) $1/1000$.

If the algorithm succeeds or fails according to inputs that are made to vary randomly across experiments concerning the same problem to solve, but independently of inputs defining the problem to solve, we can state that the scheme is broken with odds at least $1-(1-1/1000)^{1000}\approx1-1/e\approx63\%$ after 1000 experiments (raising to $\approx99.3\%$ after 5000 experiments).

Illustration: the goal is to break RSA by factoring the public modulus $N$ with $n^{5.8}<N<n^{5.9}$, which can trivially be done by trial division of $N$ in time $n^3$. Consider these two algorithms:

Algorithm $\mathcal A_0$ accepts as input $N$; it factors $N$ by trial division, and outputs the result only if $N\bmod997=42$
Algorithm $\mathcal A_1$ accepts as input $N$ and a large value $R$ randomizing the algorithm; it factors $N$ by trial division, and outputs the result only if $R\bmod997=42$

Both algorithms satisfy the stated condition. Repeating $\mathcal A_0$ 1000 times for the same random $N$ succeeds with odds just above $1/1000$; while repeating $\mathcal A_1$ 1000 times for the same random $N$ and fresh random $R$ at each run succeeds with odds just above $63\%$.

Note: if we run $\mathcal A_1$ 1000 times with incremental rather than random $R$, then success is certain.


How would I make a secret notation alphabet more secure?

A Michael Kjörling notes, what you basically have is a monographic substitution cipher.  These are generally easy to crack using frequence analysis; for example, if we know that the underlying text is in English, we can be fairly sure that the two most frequently occurring symbols correspond to the letters T and E (and that any symbol that occurs unusually often between them is probably H).

To make your cipher stronger against frequency analysis, you want to somehow make the symbol frequencies in your ciphertext as uniform (and as uncorrelated with nearby symbols) as possible.  There are many ways to do that, but the requirement that the resulting alphabet should still be something one could learn to write fluently rules out most of them.  Still, there are some things you could do:

Come up with multiple (preferably completely different-looking) symbols for the most common letters in English.  The number of symbols per letter should be approximately proportional to its frequency.  Alternate between the symbols randomly, or according to some rule of your choosing, or just as you feel like.
Conversely, consider merging some rare letters together under the same symbol(s).  This works best for letters that have shared historical roots, such as I / J or U / V / W.
Consider making up separate symbols for common or distinctive letter combinations like TH, QU or ING.  These should also have multiple variants according to their frequency.  Some particularly common words should probably have dedicated symbols.
Conversely, consider encoding rarer letters using two symbols, e.g. as the symbol for a more common similar letter plus a modifier symbol (which could be used for multiple letters to make it more common, and which could also have a stand-alone meaning or just be used as "chaff").
Introduce lots of stylistic variations to your symbols, so that it's hard for a would-be decipherer to know if two symbols are the same or not.  This is most effective if some variations (like line length, or the presence of dots or loops) are essential for distinguishing some symbols but vary arbitrarily for others.
Make it hard to tell where one symbol ends and another begins, e.g. by allowing symbols to be combined or written in unusual order.
Introduce random meaningless "chaff" symbols into your writing.
Make lots of misspellings, either more or less systematically (e.g. randomly interchange S / Z or C / K in words where it doesn't matter, spell some words phonetically or in "txt spk"), or just drop or interject random letters into words where it doesn't introduce ambiguity.
Use idiosyncratic jargon, so that even if the text is decrypted, it may still not make sense.
If you don't use dedicated symbols for common words like "the", consider substituting them with other words.  A substitution like, say, "the" → "cat" could really frustrate a cryptanalyst.
Drop unnecessary common words entirely.  You don't really need all those articles, do you?

Edit: Last but not least — don't write too much.  With enough ciphertext to analyze, any combination of these measures can still be cracked by a clever, skilled and persistent cryptanalyst.  Your best defense is making sure that there simply won't be enough text for a reliable analysis to be possible.

Oh, and never write down anything both in cipher and in plain.  Even a short bit of known plaintext in the hands of a skilled cryptanalyst can make all these tricks useless.  Look up e.g. the Rosetta stone for a historical example.


Cryptographic system with double keys with reversible order

First, remark that the desired commutativity is incompatible with security under Chosen Plaintext Attack, which (under the name IND-CPA) is considered a requirement for modern encryption systems. Proof, expanded following tylo's comment, using the IND-CPA game as played for symmetric encryption (see the CPA indistinguishability experiment in section 3.5 of Katz and Lindell's Introduction to modern cryptography, also here on page 4):

We assume a cipher $E$:

commutative as in the question, that is: $\forall a,\forall b,\forall x, E_a(E_b(x))=E_b(E_a(x))$;
injective: $\forall a,\forall x,\forall y, E_a(x)=E_a(y)\implies x=y$ (a necessity for reliable decryption);
$E$ can be deterministic or probabilistic; in the later case $E$ has some randomness source as a hidden input beyond key (the subscript) and data (the explicit parameter), and the above properties hold for all values of the random inputs in each instance of $E$;
the cipher has a public definition (except for its randomness soure if any) allowing its practical implementation by the adversary (an algorithm with time and space complexity polynomial in the size of the parameters);

the game starts with the referee choosing and announcing the size of parameters;
the referee secretly chooses a random key $k$;
the adversary chooses a random key $r$, a random plaintext $X$, and computes $M_0=E_r(X)$ using the cipher's definition, until $M_0\ne X$ (which holds with high odds for any secure cipher);
in a training phase, the adversary submits $X$ for encryption and obtains $Y=E_k(X)$;
in the challenge phase

the adversary submits $M_0$, and any $M_1$ that is neither $M_0$ nor $X$ (submitting $M_1=M_0$ would be poor strategy; submitting $M_0$ or $M_1$ that was submitted in the training phase would be against the rules of the game played for deterministic encryption);
the referee secretly chooses $i$ randomly in $\{0,1\}$ by fair coin toss, and returns $C=E_k(M_b)$;

(here the rule of the game allows the adversary to make other queries for encryption under key $k$, bound to be for messages different from $M_0$ and $M_1$ in the game played for deterministic encryption);
the adversary returns $i'=0$ if $C=E_r(Y)$, which is computable using the cipher's definition, or $i'=1$ otherwise;
the adversary wins if $i'=i$ (and we want the odds of that, which should be better than $1/2$ by some $\epsilon>0$ independent of the size of the parameters);

if the referee picked $i=0$: $C=E_k(M_0)=E_k(E_r(X))$, and applying the commutativity property of the cipher we get $C=E_r(E_k(X))=E_r(Y)$, thus $i'=0$;
if the referee picked $i=1$: since $M_1\ne M_0$, and because the cipher is injective, $C=E_k(M_1)$ must be different from whatever $E_k(M_0)$ would have been, which (as shown above) is bound to match $E_r(Y)$ that was computed by the adversary and used to find $i'$, thus $i'=1$ (note: in the case of a probabilistic algorithm, one could think there potentially could be several $E_k(M_0)$, but the commutativity property makes it necessary that they all match $E_r(Y)$ as computed by the adversary: in order to be commutative, the cipher is bound to be deterministic for inputs $M_0$ and $Y$ given how these have been generated);
thus with certainty, $i'=i$ (this is a perfect distinguisher).

As remarked by figlesquidge, XOR with a One Time Pad has the desired commutativity property, in some sense. That's also true for any Stream Cipher with an out-of-band method for synchronization (including a block cipher such as AES in OFB or CTR mode, with out-of-band IV); by out-of-band I mean: not part of the ciphertext for which the commutativity property is thought.

However the OTP or other out-of-band data is often impractical (in particular it won't work in use cases where several ciphertexts are shuffled but out-of-band data has not, which is the situation in Mental Poker), and do not match the definition of a cipher (which requires reusable key and no out-of-band data).

We study the simplest commutative cipher in the cryptographic folklore, sometime used for Mental Poker:

The Pohlig-Hellman Exponentiation Cipher

For a given public odd prime $p$, let $K$ be the set of $k\in\mathbb N$ with $0<k<p$ that are coprime with $p-1$, and $*$ multiplication modulo $p-1$, so that $(K,*)$ is a commutative group with $k=1$ the neutral element.

The Pohlig-Hellman Exponentiation Cipher over $\mathbb Z_p$ with key in $k$ is
$$\begin{align}
E:K\times\mathbb Z_p&\mapsto \mathbb Z_p\\
(k,x)&\mapsto E(k,x)=x^k\bmod p=E_k(x)
\end{align}$$

Encryption with key $k$ is $E_k: x\mapsto E_k(x)$ and is a permutation of $\mathbb Z_p$. The set of the permutations obtained form a group under function composition (noted $\circ$), isomorphic to $(K,*)$:
$$\forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p,E_b(E_a(x))=(E_b\circ E_a)(x)=E_{b*a}(x)$$
As a consequence, decryption is $D_k=E_\overline k$, with $\overline k=k^{-1}\bmod(p-1)$ the inverse of $k$ in group $(K,*)$; and the desired commutativity property holds:
$$\forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p, E_a(E_b(x))=E_b(E_a(x))$$

For appropriate $p$ (making the Discrete Logarithm Problem hard), the cipher is conjectured secure for multiple random plaintexts related to the same random key [that's stated before (15) in the original article, linked to the title of this section; and justified by an argument I do not get]. However, it has a number of other properties that a random commutative cipher would not obviously have, including the multiplicative property $\pmod p$:

$$\forall k\in K,\forall x\in \mathbb Z_p,\forall y\in \mathbb Z_p, E_k(x\cdot y\bmod p)=E_k(x)\cdot E_k(y)\bmod p$$

There are a number of other undesirable properties:

Three fixed points: $\forall x\in\{0,1,p-1\},\forall k\in K,E_k(x)=x$
A symmetry in the message space: $\forall x\in \mathbb Z_p,\forall k\in K,E_k(p-x\bmod p)=\big(p-E_k(x)\big)\bmod p$
The isomorphism with $(K,*)$ allows some related-key attacks, and implies a weak key ($k=1$).
The keyspace is not an interval of $\mathbb N$, which is inconvenient.

A variant

We can fix these 4 issues. Let $p$ be a large public prime with $(p-1)/2$ prime, such as $p=\lfloor\pi\cdot2^{2046}\rfloor+3,617,739$. Let $P$ be the set of $(p-3)/2$ integers $\{2,3\dots,(p-3)/2,(p-1)/2\}$. For key $k$ of 256 bits and data $x\in P$, define
$$\begin{align}
k_E&=2^{320}\cdot\small\text{SHA-256}(k)+2^{64}\cdot k+1\\
k_D&=\overline{k_E}={k_E}^{-1}\bmod (p-1)\\
\mathbf E_k(x)&=\min\big(x^{k_E}\bmod p,p-(x^{k_E}\bmod p)\big)\\
\mathbf D_k(x)&=\min\big(x^{k_D}\bmod p,p-(x^{k_D}\bmod p)\big)
\end{align}$$
Fixed points and symmetry are removed by the definition of $P$ and the use of $\min$. The construction of the exponent $k_E$ makes it coprime with $p-1$ (since $k_E$ is odd and too small to divide the single odd divisor of $p-1$), ensures that any 256-bit $k$ makes a fine key, and provides fair protection against related-key attacks. The construction of $k_D$ ensures that $\forall k,\forall x,\mathbf D_k(\mathbf E_k(x))=x$.

The desired commutativity property still holds, as well as the multiplicative property (be it wanted or not). We can artificially get rid of the multiplicative property by inserting a pseudo-random permutation $M$ of the set $P$ before encryption, and its reverse afterwards: $x\mapsto (M^{-1}\circ\mathbf E_k\circ M)(x)$ still has the commutativity property, but not the multiplicative property; however an adversary knowing $M$ can still potentially get advantage of the multiplicative property.

Using RSA encryption padding

If $\small\text{OAEP}(x)$ designates the padding used for RSA-OAEP with a modulus of $\lceil\log_2(p)\rceil$ bits, then $x\mapsto E(\small\text{OAEP}(x))$ seems to be IND-CPA-secure, and decipherable (the desired commutativity property is lost: that padding must be external to whatever step of the protocol requires commutativity). As pointed by Ricky Demer, OAEP+ is preferable to OAEP.

Both paddings hide the multiplicative property, by means including making the cipher probabilistic.


RSA digital signature vs authenticated cipher

You got some notation wrong. There is no algorithm like "AES-GCM-SHA-256".

AES is a block cipher, i.e. a pseudorandom permutation of 128-bit blocks. It itself only allows encryption for messages of size 128 bits (= 16 bytes), with a limited security guarantee.

When you mean "encrypt the data using AES", you actually mean "use AES with some mode of operation to encrypt the data".

Galois/Counter Mode is one such mode of operation, which combines counter mode for privacy and a block-cipher based MAC (GMAC) using some finite field operations and some block cipher calls for authentication.

SHA-256 is a hash function, but neither it nor its associated HMAC function HMAC-SHA-246 are used here in any way.

When using GCM (or almost any mode) for disk encryption with changing files, you should pay attention: You shall not use the same key and initialization vector (= initial counter) twice for different data. This also means, don't simply change some parts of the file an then encrypt again only the changed parts with same initialization vector, as you are then using the same IV twice (over time).

Instead, either generate a new random IV and encrypt the whole file with it, or split the file in blocks (of a comfortable size, e.g. 4 KB or such), each of which is then encrypted using GCM mode with a separate, independent random IV.
(This works better if you are encrypting your whole disk – then you would use the disk sector as your encryption unit.)

There is no point of using a signature – that only makes sense if you want to allow someone else to prove that you did produce (or at least sign) the data, without this one being able to produce it himself.


Either you make sure that you use separate key (pairs) for each different purposes, or you simply include all possible context in the signature, including the entities.

So sign a message consisting of "Allice: Bob, do you love me? Bob: yes".

Note that it is not required to send all the data together with the signature, as long as you can regenerate the input.

Note that low entropy is not really the issue in your question. It's the amount of context that you sign. Low entropy is mainly a problem for random number generation and the functions that rely on it, such as the key pairs themselves.


Are there ANY text strings that will generate the same SHA-512 Hash output?

This is trivially true via the pigeonhole principle. SHA-2/512 has $2^{512}$ possible outputs, but $2^{2^{128}} - 1$ possible inputs. Trying $2^{512}+1$ unique inputs is sufficient to produce at least one collision.

That said, SHA-2/512 is designed to be collision resistant, which implies that it should be hard to find two inputs that hash to the same value. Finding a way to quickly create such a collision would be considered a catastrophic break in the algorithm.

Today it is considered unfeasible to even find one SHA-512 collision - none have been found so far. There have been efforts to find a collision for SHA-1 though (notably the IAIK "SHA-1-Collison Search Graz Project"); it is thought that the SHA-1 algorithm is sufficiently broken to find one. These attacks don't translate to SHA-512 because of the increased complexity of the algorithm and the higher output size of the hash.


Will repeated rounds of SHA-512 provide random numbers?

For an adversary not knowing the definition of SHA-512 (or just not knowing the 512-bit initialization constant of SHA-512, defined as the first sixty-four bits of the fractional parts of the square roots of the first eight prime numbers), the sequence obtained by
$$\begin{align*}
H_0&=\text{SHA-512}(Seed){\small\text{ where }}Seed{\small\text{ is the statement's keyword}}\\
H_{i+1}&=\text{SHA-512}(H_i)\\
\end{align*}$$
is a Cryptographically Secure Pseudo-Random Number Generator as far as we know. It is in practice indistinguishable from random for said adversary, with residual odds of the contrary less than $2^{-100}$, assuming a few additional requirements:

Less than $2^{200}$ outputs are available to the adversary [rationale: if it happens that the generator enters a cycle, then the adversary can predict future output, including with feasibly little memory; after about $2^{(512-100+1)/2}$ iterations of a random function with 512-bit output, odds of cycling are about $2^{-100}$; I kept some margin]. Notice that producing even the first $2^{60}$ outputs would take at least five years with current technology, because this RNG and SHA-512 are a serial process [estimate based on two gate delays each one picosecond per round].
This adversary uses classical computing means bound to perform less work than needed for $2^{250}$ hash computations (a safe assumption), or anything that I can fantasize today (your call) [rationale: the best explicit attack I have enumerates the SHA-512 initialization values, and that reaches odds $2^{-100}$ to succeed at about $2^{412}$ hashes; I kept a helluva of margin]; Note: 1 and 2 can be combined into the adversary can not perform the classical-computing equivalent of counting to $2^{200}$, which is still very credible.
$Seed$ is never reused.
The adversary does not obtain the SHA-512 specification (including initialization value) by some oblique mean: reverse engineering, operating goof, spying (including bribery and planting trojans), rubber hose cryptanalysis, side channels.. [Note: reading the official specification was discounted in the first sentence].

However, with respect to an adversary knowing the full definition of SHA-512 (which is the assumption a cryptographer will make by Kerckhoffs's principles), the generator is unsafe. In particular, $H_j$ for $j>i$ can be trivially predicted from $H_i$; the generator fails the next bit test.

In addition, from a practical perspective, the generator is very bad by the mere fact that it is simultaneously

deterministic;
without another key than a keyword presumably of low entropy;
without provision for key streching to slow keyword enumeration.

If the keyword is simple enough to be reliably memorized in a real application by a majority of adult humans, then password cracking can quickly find the keyword by enumeration knowing say 10 bytes of $H_0$.

So all in all, the generator is secure for some non-cryptographic applications like numerical simulations, and disastrous from the perspectives on-topic here.


Why does this square root algorithm work?

This is Cipolla's algorithm, I believe.

The integers mod $p$ we call $\mathbf{F}_p$, and since $h^2 -4x$ is a quadratic nonresidue mod $p$, the polynomial $P(Y) := Y^2-(h^2-4x) \in \mathbf{F}_p[Y]$ has no roots. We can then mod out the polynomial ring $\mathbf{F}_p[Y]$ to get $\mathbf{K} := \mathbf{F}_p[Y]/(Y^2-(h^2-4x))$ (which by some algebra we know is isomorphic to $\mathbf{F}_{p^2}$). It is in this field $\mathbf{K}$ that $h^2-4x$ has a square root (one can think of it as the indeterminate $Y = \sqrt{h^2-4x}$)

In this extension field $\mathbf{K}$ (which is still characteristic $p$, so $(m+n)^p = m^p+n^p$ for all $m,n\in \mathbf{K}$) we have that $\left(h + \sqrt{h^2-4x}\right)^p = h^p + (\sqrt{h^2-4x})^p$.

By Euler's criterion, $(h^2-4x)^{\frac{p-1}{2}} \cong -1 \pmod p$ and Fermat's little theorem $h^p \cong h \pmod p$, and all field operations in $\mathbf{F}_p$ are the same in $\mathbf{K}$ on $\mathbf{F}_p$ elements. Therefore  $h^p + (\sqrt{h^2-4x})^p = h + (h^2-4x)^{\frac{p-1}{2}} \sqrt{h^2-4x} = h - \sqrt{h^2-4x}$.

By now, with all that math we conclude that $\left(h + \sqrt{h^2-4x}\right)^p = h - \sqrt{h^2-4x}$. The same argument also yields $\left(h - \sqrt{h^2-4x}\right)^p = h + \sqrt{h^2-4x}$.

Finally we get to the square root of $x$. Clearly $$4x = h^2 - (h^2 - 4x) = (h + \sqrt{h^2-4x})(h - \sqrt{h^2-4x}) = (h+\sqrt{h^2-4x})(h+\sqrt{h^2-4x})^p = (h+\sqrt{h^2-4x})^{p+1}$$

Now, the $k$th term of the Lucas sequence $V_k := hV_{k-1} + xV_{k-2}$ is $V_k = a^k + b^k$ where $a = \frac{h + \sqrt{h^2-4x}}{2}$ and $b = \frac{h - \sqrt{h^2-4x}}{2}$. So $$V_{\frac{p+1}{2}} = \left(\frac{h + \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}} + \left(\frac{h - \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}}$$

$$V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} \left( (h + \sqrt{h^2-4x})^{\frac{p+1}{2}} + (h - \sqrt{h^2-4x})^{\frac{p+1}{2}} \right)$$

$$V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} ( \sqrt{4x} + \sqrt{4x}) = \left(\frac{2}{2^{\frac{p-1}{2}}}\right) \sqrt{x} = \pm 2 \sqrt{x}$$


Would EdDSA be broken by replacing H(R, A, M) with H(A, M)?

This answer is assuming you are not removing the private key $a$ from the computation of $S$, and instead actually meant what is said in the title of the question:

$S = r + a H(A, M)$

Removing $a$ from the computation would be terrible.

The first issue that comes to mind is malleability, on top of collision resistance.
The signature process for EdDSA actually goes as follows:

Input: message $M$, secret key bits $(h_0, h_1, \ldots, h_{2b-1})$,
basepoint $B$  and public key point $A$

$a \gets 2^{b-2} + \sum_{3 \leq i \leq b-3} 2^i h_i$
$h \gets H(h_b,\ldots,h_{2b-1},M)$
$r \gets h\mod \ell$
$R \gets r\cdot B$
$h \gets H(R, A, M)$
$S \gets (r + a h) \mod \ell$

Return: $(R,S)$

As you can see, if you do not include the value $R$ in the hash $h$, the value $S \gets (r + a h) \mod \ell$ can easily be modified in a way that would allow to produce new signatures for the same message:

pick a random $k$
compute the point $R' = R + k\cdot B$
compute the value $S' = S + k \bmod \ell$

And you now have a new, different signature $(R', S')$ for the same public key $A$ that will verify for the message $M$.
This is possible because the value $r$ behind computed with the secret key, it is not meant to be public and is not necessary for verification. This property was used in a fault attack in 2017.
Malleability is not necessarily unwanted in cryptographic scheme, but is often frowned upon since it can very easily lead to issue with implementations.
Threshold cryptography is rough and full of dangers, and I wouldn't advise coming up with a malleable scheme as these have already proven to cause issue with threshold schemes.


Can we (with just paper and math) find the prime number "p" of an RSA key?

If there was a general strategy to do this with pen and paper, we could do it with a computer just as well. Most pen and paper solutions to any math exercise rely on using lots of “shortcuts” or “tricks” that exploit special situations or specific properties of the numbers in the problem. However, since RSA keys tend to be very big, we'd need an impossible number of special situations to have an approach that works generally.


What role does Representation Theory play in Cryptography?

Let me answer this question in the context of braid group cryptography since braid groups form the group based cryptosystems which I am most familiar with. Keep in mind that today, most if not all braid based cryptosystems have been successfully attacked. On the other hand, braid group cryptography has not been thoroughly explored and mathematicians still need to investigate braid group cryptography some more. Braid groups are very deep and interesting structures connecting diverse areas such as algebraic topology, quantum computation, and even very large cardinals, so even non-applied mathematicians should appreciate braid group cryptography enough to investigate it further.

There are several well-known representations of the braid groups including the Burau representation (which is not faithful but has a small kernel), the Lawrence-Krammer representation, and several unitary representations used in topological quantum computation. Furthermore, there are several important actions of the braid groups such as the Hurwitz action or the Dynnikov action (these actions are non-linear though). The Hurwitz action generalizes to an action of positive braids on self-distributive algebras and the Burau representation is a special case of the Hurwitz action. The Burau and Lawrence-Krammer representations can be used to attack braid based cryptosystems by first solving the problem (the problem, for example could be the conjugacy search problem) in the matrix group and then lifting the solution back to the braid groups.

The Hurwitz action on braid groups gives very easily computable strong invariants of braids which can in almost all cases distinguish braids in nearly linear time (in a sense, the Hurwitz action gives a 'hash' of a braid). The Dynnikov action can be used to solve the word problem in braid groups using only linearly many integer addition and comparison operations.

There are several ways to analyze braid based cryptosystems which have little or nothing to do with the representations of braid groups. These attacks include length-based attacks, attacks against the conjugacy search problem based on summit sets, and other attacks. Summit sets arise from the Garside normal form and Birman-Ko-Lee normal form of braids which have little to do with their linear representations. Length based attacks are based on length functions which could arise from one of the normal forms of braids. Dehornoy's handle reduction technique and its generalizations are used to minimize the length of a braid and reveal the data that braid based cryptosystems attempt to hide.

I must mention that the attacks against braid based cryptosystems are generally heuristic algorithms, so one will need to program quite a bit in order to properly evaluate these cryptosystems and to evaluate whether an attack against braid based cryptosystems is successful or not.

Since braids are related to a wide array of mathematical structures, it is easier and more direct to understand just braid groups, braid group cryptography, and how braid groups relate to certain areas of mathematics than to be an expert in all of these mathematical disciplines related to braids.

All of these representations and results about braids could be found in the standard references of braids including the survey Braid Group Cryptography by David Garber, the book Braids and Self-Distributivity by Patrick Dehornoy, the book on braid groups by Kassel and Turaev, and the book Ordering Braids by Patrick Dehornoy.


Is the concatenation of two one-way functions a one-way function?

But is h invertible more or less often? That is how I was asked the question.

When mathematicians say "This statement is not true generally" (or similar wordings) they mean "There exist cases for which the statement is false". So your teacher is talking about the statement "For all $f$ and $g$ which are one-way functions $h(x)=f(x),g(x)$ is also a one-way function" and says that this general statement is false, even if it might be true for some choices of $f$ and $g$.

Looking at this specific statement:

There are choices where it's true. You already found the trivial $f=g$.
There are choices where it's false. When $g(x)=f(x)\oplus x$, $h$ is never a one-way function, since you can recover $x=f(x) \oplus g(x)$ from $h(x)$ (technically you still have to show that there exist $f$ and $g$ of with this relation that are both one-way functions).
In practical terms, if you don't choose $f$ and $g$ deliberately to produce a weak $h$, $h$ will normally also be an OWF, but mathematicians avoid such vague and difficult to formalize claims.


How much time would it take to crack time mnemonic phrases in these scenarios?

You can calculate the number of word combinations for each possible pass phrase length and then add them together. For mnemonic phrases any order is valid, so it is a question of calculating the exponentiation of the number of words on the sheet with the number of words in the phrase.

Finally, there are two scenarios, which should be considered separately. For the first scenario there is just a single sheet of 90 words. For the second there are two sheets, but as the words do not need to be distributed over the sheets you can simply think of it as one sheet of 180 words.

Finally, if you want to know the number of bits of security you can simply count the number of digits, divide by 3 and then multiply with 10 to get a rough estimate (or perform $\log(c) / \log(2)$ where $c$ it the total number of combinations).


Unable to reproduce correct signature data

Obcrypto: note RSA-1024, although not actually broken, is no longer considered to provide an adequate safety margin and is prohibited or deprecated in most applications. For example CABforum began phasing it out in 2014, and Chrome and Firefox warned for it.

$ printf '0;2014-01-24;23:59:59;123456789;1250.00;1000.00' \
> |openssl sha1 -sign cry64393.key |openssl base64 -A; echo
gs1HumV5FxfeUum3Ws9s7ZsczPEtXUq+5/5MgYcbUb3hP9CJ2eg9d6Bm+d+D8HtbfLB3fCV8pfXo1JaluJ0JGtwLzyyC2uLDR+qvxRbCbly4W0/Ab8jPuF2KJHEPT9HLtbfwMEclMdyK+xp+OPwOvCCnREV43KMwisMGaB4TziA=
$ # or
$ printf '0;2014-01-24;23:59:59;123456789;1250.00;1000.00' |openssl sha1 -binary \
> |openssl pkeyutl -sign -inkey cry64393.key -pkeyopt digest:sha1 |openssl base64 -A; echo
gs1HumV5FxfeUum3Ws9s7ZsczPEtXUq+5/5MgYcbUb3hP9CJ2eg9d6Bm+d+D8HtbfLB3fCV8pfXo1JaluJ0JGtwLzyyC2uLDR+qvxRbCbly4W0/Ab8jPuF2KJHEPT9HLtbfwMEclMdyK+xp+OPwOvCCnREV43KMwisMGaB4TziA=

Both rsautl -sign and pkeyutl -sign with RSA key default to SSA-PKCS1-v1_5, but if you want you can specify -pkcs or -pkeyopt rsa_padding_mode:pkcs1 respectively. openssl sha1 is an abbreviation for openssl dgst -sha1 and openssl base64 for openssl enc -a.

(I can try for PHP also if you need it but that will take longer to set up.)

ADDED: I should have noted this only works because RSASSA-PKCS1-v1_5 is deterministic, which is unusual. Most other public-key signature schemes, and essentially all public-key encryption schemes (and symmetric encryption schemes also), when executed multiple times on the same data (and key) produce results which are all different but valid, so it is futile to try to reproduce or compare outputs.


Does Kasisky test for Vigenère cyphers assumption always hold?

There is imprecision in what is stated in your notes. The Kasisky test only works if the corresponding letters in the two segments are separated by a distance that is a multiple of the key length (in other words they are encrypted by the same letter in the key). For example (source Wikipedia):

[abcdea]bcdeabcdeabcde[abcdea]bcdeabc
[crypto] is short for [crypto]graphy.

Note that the key here is $5$ letters long and the distance between corresponding letters in the two segments is $20 = (5*4)$ so the corresponding ciphertext segments will also be the same. It is also worth observing that there is no need for $l \le L$ as seen in the above example.


How was the MDS matrix used in AES chosen?

They were chosen because they are the smallest non zero elements possible that make the matrix MDS and circulant. With an MDS matrix, if a single input changes, all the outputs change.

When multiplying the matrix by a value, you need to multiply the input bytes by the values of the matrix in a finite field. These multiplications have a computational cost associated with them that is related to how large the matrix values are, therefore keeping them as small as possible is a design criteria for efficiency.

Multiplication by 1 is obvious, but in the finite field used by AES, multiplication by anything else is different, since you are treating the values as polynomials.

When implemented, multiplication by 2 is a left shift with a conditional XOR, multiplication by 3 is multiplication by 2 plus XOR against the original value. Other larger numbers require more operations. Having the matrix be circulant also allows efficient operation, since you only need to perform a single multiplication per input element, and the rest is all XOR.

Multiplication can also be done in advance then use a table lookup, but that is not good for devices with very low RAM and ROM. Having the elements be small keeps the performance good for when a table lookup implementation is neither optimal nor possible.

A similar circulant MDS matrix with values 1,1,7,4 is used in the Fugue hash function which requires 2 multiplications per input element. Twofish uses 1,91,239 in a non-circulant matrix.


What is proper use of a True Random Number Generator?

I assume your TRNG has a uniform distribution and can generate all possible 32bit numbers (ie. isn't limited to a specific smaller number range, just to [0,2^32-1]).

In this case, it doesn't really matter, because the TRNG output is also a stream of truly random single bits, as well as a stream of truly random 2bit pairs (numbers 0-3), etc.
If this were not true, ie. your 32bit numbers are uniformly random but the single bits are not, it wouldn't be possible: Take the first 32bit number, then see what bits it has, and you already have information about some bits of the next numbers, meaning the full number isn't ranodm either.

So, if you take just a part of one 32bit dataset, it doesn't mean that the rest is less random anymore. Just use the rest too.


Actually, if everyone uses a different salt whenever they "sign", and if the RSA_sign operation doesn't involve a hash (in general, real signature operations do, I don't know about your variant), it turns out not to be secure, and in fact, the password can be recovered fairly easily if the attacker hears enough signatures based on the same password.

Here's how it works: when someone signs the password, what they effectively do is take their password, apply the PKCS #1.5 padding to it, forming a message $M$.  Then, they select a salt $A_i$, compute the 'signature' $S_i = (M + kA_i)^e \bmod N$, and publish the pair $A_i, S_i$ (where the value of $k$ depends on exactly how you combine the password and the salt; whether it does addition or bitwise concatination; we'll assume that the attacker can guess that).  Now, this may not be the order that the signer actually implements things, but as long as the results are the same, that doesn't matter.

Now, suppose the attacker can get $e$ different such pairs $(A_i, S_i)$, and he wants to recover the common $M$ value.  What he can do is binomially expand each such pair as:

$M^e + \binom{e}{1}kS_iM^{e-1} + \binom{e}{2}k^2S_i^2M^{e-2} + \ldots + \binom{e}{e-1}k^{e-1}S_i^{e-1}M + k^eS_i^e = A_i \mod N$

Now, the attacker knows all the above values except for $M$.  So, he can then treat these equations as $e$ linear equations in the $e$ variables $M^e, M^{e-1}, \ldots, M$ within the ring $\mathbb{Z}/N$, and find the solution for $M$, recovering the password.

Now, there are several obvious ways to break up this attack:

Use a huge public exponent $e$
Combine the password and the salt in a nonlinear way (for example, by hashing them together)

On the other hand, the existence of this attack demonstrates that you really should think twice before trying it.


Implementation details of the π step of the Keccak round function

From my implementation code, the indexes for the pi array are calculated as follows:

For x = 0 To 4
    For y = 0 To 4
        State[(0 * x) + (1 * y), (2 * x) + (3 * y)] = tempState[x, y]
    Next y
Next x

From the Keccak specification:

  The mapping $π$ is a transposition of the lanes that provides dispersion aimed at long-term diffusion. Without it, Keccak-f would exhibit periodic trails of low weight... For $π$ we have chosen a matrix that defines a permutation of the axes where they are in a single cycle of length 6.

  The mapping $ρ$ consists of translations within the lanes aimed at providing inter-slice dispersion. Without it, diffusion between the slices would be very slow. It is translation-invariant in the z-direction.

For rho offset calculation:

x = 1
y = 0

For t = 0 To KECCAK_LANES - 2
    RhoOffsets[(5 * y) + x] = ((t + 1) * (t + 2) / 2) Mod KECCAK_LANELENGTH
    newX = ((0 * x) + (1 * y)) Mod 5
    newY = ((2 * x) + (3 * y)) Mod 5
    x = newX
    y = newY
Next t

You may notice that the multiplication constants for x and y are identical to pi, and the actual computed constants are a simple geometric sequence [0,1,3,6,10,15,21,...,300] modulo 64, or whatever the lane length happens to be for smaller Keccak instances.

The reason keccak-tiny seems to use a completely different order for the rho offsets is because both pi and rho are linear and can be done in reverse order as long as the order of the offsets is changed, and that is exactly what they did. Because the order of rho is basically the inverse of pi, the fact that they switched the order makes their rho offset order identical to the geometric sequence.

So how do we see the relation between the rho offset order and the pi order? Looking at the x,y table of rho values, the 0th element (0) in the 0th position (0,0), the 1st element (1) is in the 5th position (1,0), the 2nd element (3) is in the 2nd position (0,2), the 3rd element (6) is in the 11th position (2,1), and so on, with the final element (44) in the 6th position (1,1).

Following those element positions in the sequence of the pi values within the state (x+5y), the 0th pi value is 0, the 5th value is 10, the 2nd value is 7, the 11th value is 11, and so on, with the final value being 1, matching the pi sequence table. You can calculate the pi value from the x,y position of the sequential element in the rho table, $π_{x,y}$ = $5*((2x+3y) \mod 5 )+y$

Since pi mixes the entire state by repositioning lanes, and rho rotates the bits within each lane, they are combined as a single gate free operation in hardware. The final positions of lanes within the state follows pi only.


What is the algorithm used to encrypt Linux passwords?

It's not encryption, it's a one-way hash.

There are a handful of different password hashes usually used for Linux system users' passwords, they're listed in the man page for crypt(3)

The first is the original crypt algorithm, that only supported 8 character passwords (among other flaws), and which you'll hopefully never see again.

The second is the MD5-based md5crypt ([a], [b]), marked with $1$. It's considered dated mostly because it doesn't support changing the amount of iterations, i.e. the cost of the computation.

Currently more used are the SHA-256 and SHA-512 based hashes, sha256crypt and sha512crypt, which are similar in structure to md5crypt but support variable amounts of iteration. They're marked with $5$ and $6$ respectively. As @SEJPM quickly enough commented, sha512crypt ($6$) is what at least Ubuntu and Debian currently use by default.

For $1$, $5$, and $6$, the characters after the identifier up to the next $ are the salt, which is generated randomly when the password is changed.

The remaining option, not in mainline glibc is the Blowfish-based bcrypt, marked with $2a$ (or another letter). Bcrypt also uses a salt.

For more information on password hashing, and as to why use salts and why slower is better, see
"How to securely hash passwords?" on security.SE.


Message-Recovery variant of Ed25519 signature?

Fix finite fields $k$ and $k'$, say $k = \mathbb F_p$ and $k' = \mathbb F_{p^2}$ represented by $\mathbb F_p[i]/(i^2 + 1)$ where $$p = 36 u^4 + 36 u^3 + 24 u^2 + 6 u + 1$$ for $u = -2^{62} - 2^{55} - 1$.  Fix a group $G$ written multiplicatively, say $(\mathbb F_{p^{12}})^\times$.  Fix elliptic curves $E/k$ and $E'/k'$, say $E/k : y^2 = x^3 + 2$ and $E'/k' : y^2 = x^3 + 2/(1 + i)$, with a bilinear map $e\colon E(k) \times E'(k') \to G$, say the Tate pairing.  Fix a random function $H\colon \{0,1\}^* \to E(k)$, say $m \mapsto {+}x^{-1}(\operatorname{SHA256}(m))$, where ${+}x^{-1}(x_0)$ is the point on $E(k)$ with $x$ coordinate $x_0$ and the lexicographically smallest $y$ coordinate.  Fix a point $G \in E'(k')$ of large prime order.  (This choice of curve $E/k$ and its twist $E'(k')$ is more popularly known as BN(2, 254).)

A public key is the byte encoding $\underline A$ of a point $A$ on $E'(k')$.  A signature of a message $m$ under $\underline A$ is the byte encoding $\underline\sigma$ of an element $\sigma \in E(k)$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A).$$

A private key is the byte encoding $\underline a$ of a secret scalar $a$; the corresponding public key is $\underline A = \underline{[a]G}$.  To sign a message $m$ with private key $\underline a$, the signer computes $\sigma = [a]H(A \mathbin\Vert m)$.  This yields a signature because
\begin{align*}
  e(\sigma, G)
    &= e([a]H(\underline A \mathbin\Vert m), G) \\
    &= e(H(\underline A \mathbin\Vert m), G)^a \\
    &= e(H(\underline A \mathbin\Vert m), [a]G) \\
    &= e(H(\underline A \mathbin\Vert m), A)
\end{align*}
by the bilinearity of $e$.

Note that in the choice of parameters above, a signature can be encoded in 32 bytes, or even a mere 255 bits, by combining a 254-bit encoding of an $x$ coordinate with a single bit to discriminate between the two possible $y$ coordinates.  (Further compression of the curve points may be possible with techniques like Decaf, left as an exercise for the reader.)

Thus, you have 32 bytes and 1 bit left in your budget for a 64-byte Ed25519 signature to encode a part of the message, thereby enabling message recovery of 32 bytes (plus 1 bit) in 64-byte signatures!

Let us then define a Mr. Signature as a 64-byte string $\underline \sigma \mathbin\Vert m$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A),$$ which admits message recovery by $\underline \sigma \mathbin\Vert m \mapsto m$.

(Am I joking?  Maybe!)


test vectors for 3DES seem to in fact be testing DES - not 3DES

It is for the 1st version of 3DES which is only using the same key three times (3DES-EDE1)

Which is equivalent to DES (I think they did that so you could use 3DES to exchange with someone using DES).

There are 3 different versions (or ways of using DES). EDE3 is the strongest with 3 different keys being used.


As far as we know, SHA512 acts like a random function.  So, the only way we know to find a preimage whose hash starts with 0x12345678, is to go through distinct preimages, and hash each one until we find one that starts with 0x12345678.

If the output of SHA512 is equidistributed (and we have no reason to believe it isn't), then the probability of any hash starting with 0x12345678 is $2^{-32}$, hence the expected number of hashes you would need to perform is $2^{32}$, which is an achievable work effort.


Combining secret keys into a single shared key

Secret sharing is a perfect tool for this application. Under any linear secret sharing scheme, individuals can generate shares of secret values to distribute to other parties involved in the scheme. Once each individual has distributed shares of their secret value to all the other parties, due to the linearity of the scheme they can each locally sum the set of received shares and the collectively hold a valid share of the summation. This is because, by definition, linear secret sharing schemes possess and additive homomorphism, meaning that adding shares yields shares of a value which, if revealed in a reconstruction process, is identical to the value of the summed secrets.

In a more detailed manner, illustrated with additive secret sharing, every party $P_i\ \forall i\in Z_{n+1}$ generates $n$ random values in some valid group denoted by $m$ which will serve as shares of the secret $x_i$ for all the other player i.e. $[x_i]_{\mathbb{Z_m}}^{P_j}\in_R\mathbb{Z}_m \ \forall i,j\in Z_{n} $ and the final share satisfies the following equation $[x_i]_{\mathbb{Z_m}}^{P_n}=x_i-\sum_{j=0}^{n-1}[x_i]_{\mathbb{Z_m}}^{P_j} \mod m$. Then every party $P_i$ sends $[x_i]_{\mathbb{Z}_m}^{P_j}$ to all other parties such that $i\neq j$. Finally, the parties all locally compute the following summation locally in which $x_\Sigma$ denotes the summed secrets.
$$ [x_\Sigma]_{\mathbb{Z}_m}^{P_i} = \sum_{j=0}^{n}[x_j]_{\mathbb{Z}_m}^{P_i}\mod m$$

Now each party holds uniformly random and information theoretically secure shares of the sum of their individual secrets and all parties must cooperate to reveal the underlying value. Specifically they would have to communicate all their individual shares to one another then they could each locally calculate:
$$x_\Sigma = \sum_{i=0}^{n}[x_\Sigma]_{\mathbb{Z}_m}^{P_i} \mod m$$

I encourage you to look deeper into secret sharing in general as well as other schemes, Shamir's secret sharing scheme in particular, due to the resilience it can introduce to a system in the presence of active adversaries or component failures.


Is CBC still better than ECB if the key and a large part of the texts are random?

After observing many transactions the ECB will likely break. The random data is not likely to repeat. Any repeating cipher blocks will be from the data revealing both the location in cipher stream and the fact the matching plain text was the same in both messages.
Encrypting only the small message with CBC and a random IV will be faster and more secure.


How many degrees of freedom up my sleeve?

Actually, given that the MD2 S-box needs to be a permutation, using a Fisher–Yates shuffle does seem a fairly obvious choice to me.  (It's pretty much the standard algorithm for generating a uniformly chosen random permutation.)  The rand() function used to convert the digits of $\pi$ into a random number from a given interval looks complicated, but is also a fairly standard method.  (IIRC, it's essentially the same as what's described in Fisher and Yates' original book from 1938.)

That said, you asked about the number of degrees of freedom available, so let me try to count the various plausible choices one might've made in generating the permutation:

The first obvious choice is the base in which $\pi$ is expressed.  The Rivest code uses base 10 digits, but since we're using a computer, at least the bases 2, 16 and 256 would've made sense (and using base-256 would've even allowed the rand() function to be simplified).  That's four choices, or two bits of freedom.
Also, using only the fractional part of $\pi$ (i.e. skipping the first digit) would've probably been a plausible choice.  That's one bit of freedom.  One might've even been able to justify the use of $\tau = 2\pi$, or its fractional part, for another bit of freedom.
Obviously, there are plenty of other "obvious" irrational constants besides $\pi$ that could've been chosen.  This excellent paper by D.J. Bernstein et al., mentioned by Seth in the comments above, lists 17 such constants: $\pi$, $e$, $\gamma$, $\sqrt2$, $\sqrt3$, $\sqrt5$, $\sqrt7$, $\log(2)$, $\varphi = (1+\sqrt5)/2$, $\zeta(3)$, $\zeta(5)$, $\sin(1)$, $\sin(2)$, $\cos(1)$, $\cos(2)$, $\tan(1)$ and $\tan(2)$.  (Adding $\tau$ makes it 18.)  Each of those has a reciprocal, and either the original constant or the reciprocal has a non-zero integer part that can be dropped, multiplying the number of possible constants by three, for a total of $18 \times 3 = 54$ possible choices, or $\log_2 54 \approx 5.8$ bits of freedom (including the two bits from the previous bullet point).
The Fisher–Yates shuffle has an "inside-out" version, which produces a different permutation for the same input.  Also, either of the variants could be started from either the top or the bottom end of the array, yielding different results.  That's two more bits of freedom.
The rejection sampling used in rand() could've been avoided by expressing $\pi$ in a mixed-radix system (with the base increasing or decreasing by one for each digit).  Such a choice (which essentially amounts to a form of arithmetic decoding) could've been justified by the fact that it minimizes the amount of input "randomness" required to generate the needed pseudorandom digits.  As there are at least two reasonably natural ways to do this (increasing or decreasing radix), we can increase the possible bases from four to six, giving us an extra 0.6 bits of freedom.

Putting all of these choices together, we have $4 \times 54 \times 6 = 1296$ reasonably plausible combinations to choose from, giving us at least $\log_2 1296 \approx 10.3$ bits of freedom.

Of course, if that's not enough, there are various other methods we could try, such as "accidentally" implementing Sattolo's algorithm or one of the many other subtly biased (but still pretty convincingly random) variants of the Durstenfeld–Knuth–Fisher–Yates shuffle.

We might even be able to appeal to tradition and use Fisher and Yates' original algorithm instead of the Durstenfeld variant, perhaps combined with simple rejection sampling for the first half (as originally suggested by Fisher and Yates), or perhaps the algorithm by C.R. Rao described in later editions of their book.  Or we could even just go with pure rejection sampling (i.e. take the base-256 digits of $\pi$ and discard duplicates), or maybe some variant of the sort-by-pseudorandom-key method of generating permutations (which should allow plenty of freedom in how to generate the keys).


Can the Smart-Vercauteren Homomorphic Encryption be implemented as a practical fully homomorphic encryption scheme?

The SV scheme made some significant simplifications that turned out to hurt security.  Specifically, it's known how to break the scheme in subexponential time (roughly $2^{n^{2/3}}$) in the dimension $n$ of the lattice defined by the public key.  Moreover, it's known that the scheme can be broken in polynomial time by a quantum computer.  In short, the reason is that the SV scheme has an ad-hoc method of key generation, which tends to produce "weak" ideals that can be attacked more efficiently than arbitrary ideals.  See this paper for further details.


Why are there $ signs in my passwd file?

Crypt based password hashes have several parts separated by $

The hash type, 1 in your case, this stands for MD5-crypt (this is not plain MD5)
The salt, hdhxObPx in your case
The actual hash TYFuTKsB9GGIgo53rF4bi1 in your case
Some schemes have additional parameters, such as a work-factor, but this does not apply to the scheme used in your example.

The MD5-Crypt scheme should be avoided, in favor of modern schemes, such as bcrypt (usually starting with $2a$). Not because MD5 is cryptographically broken, but because it has a constant work-factor, that's too small for the computational power modern attackers can field.

Check out crypt (C) on Wikipedia for further information.


Authentication protocol for communication with Arduino Uno

I am going to assume we're at the application layer here and you're implementing end-to-end (E2EE) encryption.

A public key infrastructure (PKI) could help solve the mutual authentication issue. Without more detail of the project, here is one way to accomplish this.

Both Arduinos and Android share a trusted certificate authority (CA).
Arduinos or Android create their own keys and send a certificate signing request (CSR) to the CA.
CA signs the CSRs and returns them to their respective devices.
Arduinos and Android can now mutually authenticate with each other during ECDH (or maybe even ECDHE).

Here, you're essentially mimicking how TLS provides authentication and confidentiality, but at the application layer. Session Ids can be created by using a secure hash function with your shared secret and some other data. That data will depend upon what you want your session ids to provide (constant ids, unique ids, etc).


Why does the server in S/KEY authentication only store a single password?

Applying the hash function assures that only the next password in sequence will be valid.  There is no reason to store the previous state, or the client's original secret.  Once a valid key is used, the server stores the hash of it (which is the same algorithm used to generate the list of hashes in the first place.)  This puts the burden of storage on the client, meaning the server doesn't need a 1000 rows in the database for each user.

Of course, this algorithm was developed in the days before hardware boxes capable of testing 1.5 trillion hashes per second were commercially available.


$\boxplus$- key addition vs $\oplus$- key addition

As pointed out in the comments, one attraction of mixing $\oplus$ and $\boxplus$ is that it makes cryptanalysis harder due to non-associativity.

The differential properties of $\boxplus$ were analysed here and you can find out more by chasing citations to this paper. Massey's PHT (Pseudo Hadamard Transform) is also of interest and was used in SAFER and Twofish.

In terms of key addition using $\boxplus$, the diffusion is slower than XOR when there is no carry, with no added benefits and that is probably why it is not used widely. And the somewhat annoying fact that during decryption, to undo addition of $k$ you must subtract it.


Why is it necessary a prime factor recovery for a RSA Key-Pair Validation (in case of fix public exponens)?

I don't understand why is necessary if $p$ and $q$ are known during in generation.

Because rsakpv1-basic may be run by something that's not the key generation process; it is there to allow this second party entity to validate things.
We generally keep $p$ and $q$ in the private key (along with the other CRT parameters); 800-56B is apparently envisioning scenarios where we don't.


The concept of language has been systematized. For example here you can become familiar with this in an accessible way.

In the article you are reading the language has such meaning:

Wikipedia BQP:

  A language L is in BQP if and only  if and only if and only if there exists a polynomial-time uniform family of quantum circuits   $\{Q_n:n \in \mathbb{N}\}$, such that

  For all $n \in \mathbb{N}$, ''Qn'' takes ''n'' qubits as input and outputs 1 bit
  For all ''x'' in ''L'', $\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}$
  For all ''x'' not in ''L'', $\mathrm{Pr}(Q_{|x|}(x)=0)\geq  \tfrac{2}{3}$

  Alternatively, one can define BQP in terms of quantum Turing machines. A language L is in BQP if and only if there exists a polynomial quantum Turing machine that accepts L with an error probability of at most 1/3 for all instances.


Do I need to send the RSA public exponent with the public key?

RSA key pair generation can be performed with a static $e$ or with an $e$ that is calculated after the private key has been calculated. Generally software chooses to perform the calculation using a set public key, the fifth prime of Fermat (F4 where 4 is the index) with that value 65537 (0x010001 in hexadecimals).

For compatibility reasons it is generally preferred to allow more values than just F4,  even if your own software only uses F4 for key pair generation. However if you are writing your own closed protocol then setting a static value such as F4 for $e$ is perfectly fine. Note that you may however still preclude some (admittedly weird) libraries / hardware solutions that generate random 16 bit values of $e$.

The RSA public key format is specified in PKCS#1. Most libraries will able to handle this key format and/or the SubjectPublicKeyInfo format found in X.509 certificates (this format contains the PKCS#1 format, but additionally indicates the type of key). So one advantage of leaving it in there is direct software support. Furthermore, you are also freed from thinking about how to encode the modulus & length of the modulus (in case multiple key sizes need to be supported).

Here is the ASN.1 module from PKCS#1 Appendix C:

RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}

So even if you do only use one value, it is a question if you don't want to send the value of $e$. In the end you'll just save 3 bytes not calculating overhead and to 9 to 12 bytes if you include all the ASN.1 overhead that is required to split the modulus and the exponent. If space is at a premium you may want to switch to elliptic curve cryptography (ECDH or ECIES) because of the smaller key sizes.


Can ECB mode really leak some characters?

The article mentions that 3-DES was used to encrypt these passwords in ECB mode. DES has a 64-bit/8-byte block.

So let's say you use ECB to encrypt a nine byte password. The first 8-bytes are encrypted using ECB. So far so good.

But what happens when we come to the ninth byte? Well we're now in a new block but only the first byte is populated with any data. The rest are zeros (assuming no padding is used).

This means that there are only 256 possible encryptions of the second block for all nine byte passwords. With a large enough database, it will be relatively easy to guess what these encryptions are. If you had a dictionary of common nine character passwords, a mere frequency analysis of the last character of the password and a comparison to the frequency of the second ECB blocks would be enough!

So yes, the paragraph is correct. It's a significant hole in the scheme they used.


Then, the tag (m,t) is a valid MAC for the message IV.

In other words, given a tag $(IV,t)$ for a message $m$, you can construct a tag $(m,t)$ for the message $IV$. So your understanding is wrong. It is not $m\oplus m$ in the forgery, it is $IV\oplus m$ which is the same as $m\oplus IV$.


We recently discussed this question with some colleagues, and this is what we came up with (no guarantees):
Grover's algorithm only outputs a correct answer if it is fed with an input set such that the target function evaluates as 1 for a single input and as 0 otherwise. The algorithm then iterates a subroutine $\sqrt{N}$ times (where $N$ is the size of the input set) to push the amplitude of the input that evaluates as 1 up. That way, the correct input is measured with a high enough probability (sorry for being vague at this point).
To use Grover's algorithm to attack a hash function's preimage resistance, you select a random subset of inputs and hope that there is one input that is actually a preimage of the target value (I guess a small number of preimages should also be OK, as all their amplitudes should be pushed up and eventually one of these is measured). Now, the runtime of Grover's algorithm depends on the size of the input set $N$. So, we want to keep this $N$ small. On the other hand, we have to select $N$ such that with significant probability there is a preimage in this set. In general, it is assumed that we need to take $N$ in the order of the output size of the hash function to get this probability high enough.
If we want to parallelize this, it should work as follows. Assume we get a quantum computer with twice the number of qubits needed to run Grover with an input set of size $N$. In that case, we can run it on two input sets of size $N$ while still taking only time $\sqrt{N}$. However, the benefits are also only linear, the probability of finding a preimage (or rather the probability of finding an input set containing a preimage) is only doubled.
Of course, we could also run it with an input set of size $N^2$, increasing our success probability exponentially, but this also increases the runtime exponentially.


Your protocol is good (assuming an honest-but-curious adversary model). As DrLecter pointed out, each party will need to publish their sum of shares. To recover the answer, each party then simply xors all published values.