How well is it understood mathematically why encryption schemes are hard to crack?

...I know that encryption is all based on two principles of "confusion" and "diffusion"

Symmetric algorithms such as block ciphers, hash functions, and stream ciphers are based on these principles. One Time Pads are not. And asymmetric algorithms are not built from these principles, though they may end up possessing them anyways.

  ... but these are very general, handwavey principles

Actually, diffusion is pretty well defined. There is the avalanche effect, which says that flipping one input bit should result in approximately one-half of the output bits being flipped. There is also the notion of branch number.

"Confusion" is a bit more nebulously defined, although there do exist s-boxes that are known to provide optimal stats against known cryptanalytic techniques.

  So that's why I'm wondering: what is our current formal mathematical understanding of what makes encryption schemes secure?

You'll have three different answers, depending on whether or not you're talking about One Time Pads, symmetric ciphers, or public-key encryption.

One Time Pads

One Time Pads are information-theoretically secure, which means that no computational algorithm operating on the ciphertext can help you to learn anything more about the plaintext than what you already know, irrespective of advances in computational power or clever algorithms

Unfortunately, they are too cumbersome to use in practice

Symmetric ciphers

A good symmetric cipher is designed to resist all known attacks, such as linear and differential cryptanalysis.

However, "all known" attacks is certainly not a formal proof that no (publicly) unknown attacks exist that could break a given algorithm.

Proving that an algorithm is computationally secure means a proof that breaking the algorithm implies the ability to break a problem that is known to be hard. No typical block ciphers carry proofs of this sort.

That does not mean they carry no proofs at all. For example, AES has proofs for resistance against known attacks.

Asymmetric algorithms

Asymmetric algorithms are built from problems that are assumed to be hard.

"Assumed to be" might seem unsatisfactory; Unfortunately, that's the best anyone can do until the $\text{P}$ versus $\text{NP}$ debate is proven one way or the other.

This is a major open problem in the world of computer science: If you solve it, you can claim a $1,000,000 prize (and most likely a place as a legend in the history of science and mathematics too).

If $\text{P} \neq \text{NP}$, which is what many people believe to be the case, then cryptosystems built from problems in NP would be secure.

If $\text{P} = \text{NP}$, then it is not necessarily the case that all cryptosystems would be insecure in practice. Such a proof might:

Only prove the relationship between the problem classes, without actually constructing an algorithm that solves $\text{NP}$ problems in polynomial time.
Even if such a proof were constructive and included such a polynomial time algorithm, the running time of that algorithm could still be something like $O(n^{1000})$, which would be unhelpful for solving such problems in the real world.

Impagliazzo's Five Worlds

For more on how things would be depending on the $\text{P}$ versus $\text{NP}$ question, you might check out Impagliazzo's Five Worlds. It details what type of world we would live in depending on which relationship is true.


Are Paillier and El Gamal encryption schemes secure against quantum attacks?

Sure there's a difference between Paillier and ElGamal as opposed to lattice-based cryptography regarding quantum attackers.

Paillier's security is broken as soon as you can efficiently factor large integers which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by factoring $n$.

ElGamal's security is broken as soon as you can efficiently compute discrete logarithms which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by finding the $x$ such that $\alpha^x\equiv \beta\pmod p$ given everything but $x$.

With lattice-based schemes it's a bit more interesting. Some schemes, like NTRU, can hold up against quantum attackers, while others not so much, like one invented and broken by GCHQ (PDF).


Use R-CTR (randomized counter mode) to compute MAC

I'll assume that R-CTR is CTR with a random IV or nonce.

Counter mode cannot be used to compute a MAC for the simple reason that the ciphertext of any part of the plaintext does not depend on any other part of the plaintext.

With CBC the ciphertext over the previous block is used as input (vector) for the next block encryption; it is XOR-ed with the next block of plaintext before it is encrypted. This means that the last block of ciphertext depends on all previous blocks. This makes it possible to create MACs such as CBC-MAC and the more secure CMAC out of CBC mode encryption.

Counter mode first creates a key stream which is then directly XOR'ed with the plaintext to produce the ciphertext. This means that each and every bit of plaintext is encrypted completely independently of any other bit of plaintext. So in the end you're just as far as you were before.

I cannot explain how you could combine CBC-MAC and R-CTR to create a MAC without seeing the definition of this scheme. In principle you'd just need CBC-MAC or course, even if that requires that the length can be determined in advance.


What is the "shared secret" used for in IPSec VPN?

Most likely, this 'shared secret' was actually an IKE "preshared key"; it is used to authenticate the two sides (and, for IKEv1, is stirred into the keys).  It actually isn't used as a key (and hence someone learning that key cannot use it to listen in, unless they perform an active Man-in-the-Middle attack).

I suspect the password is the authentication credential to the remote operating system; it doesn't get involved with the encryption at all.

Now, if you're asking "how is this IKE preshared key" used, well, I'll try to outline it for you; the bottom line is that someone with the preshared key cannot listen in (or be able to decrypt previously captured sessions).  They would be able to perform a man-in-the-middle attack; that's because the preshared-key works as authentication data; someone with it can impersonate.

To make this even more complex, there are two different version of IKE (IKEv1 and IKEv2), and they use the preshared key somewhat differently.  Since I don't know which one you're using, I'll list how they both work separately.

For both versions of IKE, the negotiation happens in two phases; the differences (that you care about) occur in the first phase (which generates the IKE SAs; that is an encrypted control channel that the two sides use to coordinate things).

Here's how the first phase of IKEv1 works (assuming that you're using preshared key authentication, and omitting the parts not relevant to the key generation):

The two sides exchange nonces
The two sides perform a Diffie-Hellman exchange
The two sides each take the nonces, the Diffie-Hellman shared secret and the preshared key), and generate a set of IKE keys
They exchange IKE encrypted messages (to verify that both came up with the same IKE keys; if they used different IKE keys, they won't).

For IKEv2, this first phase looks like:

The two sides exchange nonces
The two sides perform a Diffie-Hellman exchange
The two sides each take the nonces, the Diffie-Hellman shared secret, and generate a set of IKE keys
Via IKE encrypted messages, they exchange authentication data.  For preshared key authentication, this is a complex (noninvertable) function of the preshared key, and the keying data.  The idea is that if there was a man-in-the-middle who didn't know the preshared key, the keying data between the actual two sides woudl differ, and the man-in-the-middle wouldn't be able to adjust this authentication tag to account for that).

Now, for both IKEv1 and IKEv2, they perform the second phase; they generate the IPSec SAs, which are the keys (and other data) used to actually encrypt the traffic.  To do this, they exchange SPI values and nonces, possibly do another Diffie-Hellman exchange, and they create the IPSec keys from some IKE keying data, the SPI values (and the Diffie-Hellman shared secret, if a Diffie-Hellman was used.

Now that the two sides have the IPSec SAs established, they can now send and receive encrypted traffic.

And, because a Diffie-Hellman operation was involved, someone listening into the traffic is unable to decrypt anything; even if they know what the "preshared key" was.

From the fritzbox website on "VPN for experts":

  IKE negotiation takes place in two phases. The first phase serves to
  establish an encrypted connection; in the second phase the actual VPN
  tunnel is established - already encrypted. Special authentication
  procedures ensure that no password or key is transmitted in plain text
  during the negotiation. A hacker tracing the establishment of the VPN
  connection using IPSec cannot procure any security-sensitive
  information.


The entropy of passwords is not universally distributed. So hashing can be used to concentrate the input of a hash.

The concentration of entropy from another source is called extraction by HKDF, which is a key based key derivation function (which should not be used for passwords). This is from the introduction of RFC 5869, which defined HKDF:

  Thus, the goal of the "extract"
     stage is to "concentrate" the possibly dispersed entropy of the input
     keying material into a short, but cryptographically strong,
     pseudorandom key.

Now the problem with passwords it that they usually does not contain enough entropy or randomness. The size of a password is an important part of estimating the strength of a password. If a password has enough entropy then you could even use a KBKDF such as HKDF or a hash directly. But the table on the same Wikipedia page shows that you would need 20 fully random printable ASCII characters to accomplish a 128 bit security level.

Instead what is used is a Password Based Key Derivation Function or PBKDF. The usage of such a function is often called password hashing to distinguish it from directly applying a hash over the password. Common implementations are PBKDF2, bcrypt and scrypt. The PBKDF uses password stretching to accomplish password strengthening. It adds at least two input variables besides the password: a salt and a work factor.

So to get back to your question:

don't use a normal hash for password hashing, use a password hash/PBKDF;
the more randomness in the password, the better - this usually means longer hashes not shorter ones;
the size of the password is not in any way limited by the (password) hash function.

A human will never - in real life scenarios - remember a password or care to type in a password that contains enough randomness to reach the security level provided by even the least of the hash functions (MD5).

In the end it doesn't really make sense to limit the size of passwords unless for backwards compatibility reasons. The minimum size should be controlled however, and as many possible additional measures should be taken to protect the password as passwords are inherently weak.


Yes.  Use append-only logs, or a cryptographic timestamping service.  These approaches are generally designed to solve the problem you mentioned, namely: detecting tampering with data or post-dating of old data.

See the following resources on this site and our sister site, Security.SE:

Techniques for ensuring verifiability of event log files
WORM media types
How are timestamps verified?
On-line cryptographically signed date/time?
Signature and Timestamp for Long Term Document Archival Question
Geographic equivilent of RFC 3161 (X.509 PKI Time-stamp Protocol)

They should cover this topic in great detail.  Enjoy!


Differential bound of the S-Box in GOST R34.11-2012

Differential bound of the sbox is an upper bound on the probability of the differential characteristic below, i.e.,
$$P(S(x_1) \oplus S(x_2) = b | x_1 \oplus x_2 = a)\leq \frac{8}{256},$$
for all $a,b.$

A differential used for cryptanalysis is assembled by joining different differential characteristics from different rounds. This results in a number of Sboxes being 'active', i.e., taking part in the overall differential.

However the probability of a differential would be upper bounded only by
$$(8/256)^k$$
where $k$ is the number of active sboxes that are part of the differential. If there are nontrivial attacks, this $k$ will be much smaller than 64.


Verifiable, Distributed Secret Santa Assignments

Reform the problem. Instead of each participant picking their givee (which they give to), have them select a giver (which they receive from).

Each participant randomly generates a number (appropriately large) and anonymously submits it (e.g., via the tor network) to the site. This number represents them as giver.
After all participants have entered, the site publishes the list and participants (1 at a time, in no particular order) select (and remove) a random number from the list, linking it with their public name as a recipient to the giver-id.
After all participants have selected a giver-id for themselves, the validity criteria is evaluated: Each participant observes the specific co-participants with whom they conflict (i.e. immediate family members). If a conflicting co-participant possesses the observer's giver-id, that observer anonymously (via same channel as in step 1) registers a conflict.

If no conflicts occur, each participant now knows to whom a gift should be given: the co-participant possessing their giver-id.
If one or more conflicts occur, start over at step 2 with the restriction that participants cannot chose the same giver-id as before.
If all combinations are exhausted, start over at step 1 by re-choosing giver-ids.

The probability of success and/or expected iteration count is left as an exercise for the reader.


Finding a secret cipher given the key and known plaintext?

As fgrieu hints at in the comments, it is not in general possible to find $\operatorname{Enc}$. Otherwise you would be able to break an arbitrary block cipher, because the key of any block cipher can be cast as part of the algorithm instead.

Even if you ignore the computational cost, there is no way to find $\operatorname{Enc}$ given values for only one $k$, even if you know all pairs $x, y$ for that key. There is of course a limited number of (distinct) $n$-bit block ciphers with $l$-bit keys, but the different keys can be completely independent.

For example, I could define AES' which works just like AES, except with the key value $42$ it performs the identity permutation instead. You could not know that difference from observing the outputs for any other keys.


Neither.

There is no such a thing as a strong input message to a secure hash function.

Hash functions don't take a key as input. Keys could be used as input to a KBKDF such as HKDF to derive additional keys key secrets. Those algorithms are often build from hashes though.

The output of a secure random bit generator doesn't need to be hashed to be secure. Many PRNGs / DRBGs are actually build from secure hash functions. Adding a single hash won't help.


It's merely an update to align the hashing algorithms. There are in fact no real "consequences" which might have any negative impact as the v2.1 schemes are still supported. The positive impact is the alignment with FIPS 180-4.
To quote the revision history at page 59 of "PKCS #1 v2.2: RSA Cryptography Standard":

Version 2.2 updates the list of allowed hashing algorithms to align them with FIPS 180-4, therefore adding SHA-224, SHA-512/224 and SHA-512/256.
The following substantive changes were made:
— Object identifiers for sha224WithRSAEncryption, sha512-224WithRSAEncryption and sha512-256WithRSAEncryption were added.
This version continues to support the schemes in version 2.1


The salt is not required to make HKDF secure. Using a static salt doesn't make too much sense - you should be perfectly fine with using an empty salt. Either you can use an empty salt, or a new random salt. This salt could be generated and prefixed per file. If it is large enough (say 128 bytes) then it would make each encryption key unique so you don't have to depend on filename or other meta information (that could be part of Input) to derive the file encryption key.

The salt makes the HKDF function easier to proof, but I haven't heard on any attacks on KDF's without it - including those that directly use a hash function while they should not.

There is little need to perform the extraction of key material from the output of scrypt. Basically you can already create a key from the output of scrypt. So there is no need to derive the pseudo-random key (PRK) for using HKDF-extract. That way you should be fine with just applying HKDF-expand, making the calculations slightly less computationally intensive.

So you would have:

IKM = scrypt(password, salt1)
K = HKDF-expand(IKM, Input, 256)

where Input is any canonically encoded information that defines the file to be encrypted.

You could also go for:

IKM = scrypt(password, salt1)
PRK = HKDF-extract(IKM, salt2)
K = HKDF-expand(PRK, Input, 256)

In this case Input can even be empty if salt is random enough. The salt can be stored (prefixed) with the encrypted file.

Note that salt1 is used for scrypt which according to the org. answer of your previous question should only be used once. Therefore it cannot be used for HKDF.


Diffie-Hellman Key Exchange in $GF(2^5)$

To summarize, we are considering a DHKE in $GF(2^5)\cong GF(2)[x]/(P(x))$ where $P(x)=x^5+x^2+1$. The generator element is chosen to be $\alpha=x^2$. There are two parties, let's say $A$ and $B$, with private keys $a=3$ and $b=12$.

First off, I would suggest to compute the public keys of both parties. They are, by definition, $\alpha^a$ and $\alpha^b$. Then there are two equivalent ways to compute the shared secret. That is, either $\left(\alpha^a\right)^b$ or $\left(\alpha^b\right)^a$. Note that the result is not $x^{2^{36}}$.

Then you have to remember that you are working modulo $P(x)$. That is, $x^5=-x^2-1=x^2+1$ inside $GF(2^5)$. We can use this to "break" down polynomials. For example, $$x^6=x\cdot x^5=x\cdot(x^2+1)=x^3+x$$
or $$x^{10}=x^5\cdot x^5=(x^2+1)\cdot(x^2+1)=x^4+2\cdot x^2+1=x^4+1.$$
Applying this technique to $\left(\alpha^a\right)^b$ or $\left(\alpha^b\right)^a$ gives you the correct result.


PRP vs PRF for the F-function of a Feistel network

Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions?

No.

  What are the theoretical cryptographic implications of using a PRP instead of a PRF?

We have a bound for the security of Luby-Rackoff based on the PRF-Security of F.
We have a bound on the PRF-security of a PRP ("PRP/PRF-Switching-Lemma").
We can simply plug one into the other to get our answer!

So, first the switching lemma:

  Let $E:\mathbb K\times \mathbb X\to\mathbb X$ be a family of permutations and $N:=|\mathbb X$|. Further let $\mathcal A$ be an efficient adversary against the PRF-security of $E$ making $q$ queries. Then there exists an adversary $\mathcal B$ such that $$\mathbf{Adv}^{\text{PRF}}_E(\mathcal A)\leq \mathbf{Adv}_E^{\text{PRP}}(\mathcal B)+\frac{q^2}{2N}.$$

Now the Luby-Rackoff-Bound (for three rounds):

  Let $F:\mathbb K\times \mathbb X\to\mathbb X$ be a family of functions with $N:=|\mathbb X|$. Further let $\mathcal A$ be an efficient adversary against the PRP-security of $\operatorname{LR}(F)$ making $q$ queries, then there exists an adversary $\mathcal B$ such that
  $$\mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(F)}(\mathcal A)\leq 3\cdot \mathbf{Adv}_{F}^{\text{PRF}}(\mathcal B)+\frac{q^2}{N}+\frac{q^2}{N^2}.$$

And now finally the combined bound:

$$\mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(E)}(\mathcal A)\leq 3\cdot \mathbf{Adv}^{\text{PRP}}_E(\mathcal B)+\frac{3q^2}{2N}+\frac{q^2}{N}+\frac{q^2}{N^2}$$

So as you can see, nothing substantially changed here.

The switching lemma and the luby-rackhoff bound can eg be found in the Boneh-Shoup book.


You would prove it the same way that you prove encrypt-then-MAC in general. In fact, since there are already generic proofs of the encrypt-then-MAC paradigm, and since AES-CTR is already proven as being CPA-secure, all you really need to do is to prove the security of GMAC as a MAC, and then you can apply the general theorem. However, note that your assumption about AES-GCM MAC tags is not an acceptable one. You cannot assume that the "best" is brute force. Rather, you have to take the security based on AES.

Note also that you are better off proving that it achieves authenticated encryption, since this is stronger than CCA security.


What does the "description of group $G$" includes?

My question is what does this description includes?

The information that describes what elements are in the group, and how to perform the group operation.  In a $\mathbb{Z}_n^*$ group, the value $n$ may be sufficient, for an Elliptic Curve group, that'd include the curve equation (e.g. for Weierstrass curves, the values $a$, and $b$ in the equation $y^2 = x^3 + ax + b$), and the finite field the group is defined over.  Actually, in practice, we typically don't generate curves on the fly; it is far more typical to say "I'm using P256" or "I'm using Curve25519".

  Is it because for example in RSA the group elements are known before

No, it's because that the group $\mathbb{Z}_n^*$ has additional properties that generic groups don't have, and an attacker can exploit these properties to make solving the discrete log problem faster.

One such property is that fact that we can construct a modest-sized list of elements $p_0, p_1, ..., p_i \in \mathbb{Z}_n^*$ such that, given a random element of $x \in \mathbb{Z}_n$, we have a nontrivial probability of being able to quickly find the values $e_0, e_1, ..., e_i$ such that $x = p_0^{e_0} \cdot p_1^{e_1} \cdot ... \cdot p_n^{e_i}$; we don't know how to do that with a generic group, and it turns out to be useful in the discrete log problem.

And, in case you're wondering what that quick algorithm is, well, we set $p_0, p_1, ..., p_i$ to the first $i+1$ primes, and given $x$, we treat it as an integer (rather than an element of $\mathbb{Z}_n^*$) and do a quick factorization on it, using an algorithm that is designed to be find small factors (and if it fails because of a large factor, we can detect that quickly).  A nontrivial fraction of $x$ turn out to be smooth, and hence this works sufficiently often.


RSA: How to calculate the private exponent?

If I'm understanding your question right, you want to obtain $d$ from given $n$ and $e$.

You'll have to factor $n=33=3*11$ and as $N=p*q$ you have obtained your $p=11$ and $q=3$. Now proceed as usual with calculating the inverse.

As pointed out correctly above, you can't easily generalize this approach to larger numbers as factoring $n$ will be infeasible. Now you see how to factor the number but for larger numbers even the best algorithms fail. Concerning your $e=3$ I'd consider using Coppersmith's attacks on low exponent RSA.


Cracking an RSA with no padding and very small e

If there is no padding, then you can try the following:

You can run an exhaustive search on the possible plaintexts. No padding means no randomness; encryption is deterministic, so you can "try" plaintexts and see if one matches the encrypted value when encrypted.
Without padding, encryption of m is me mod n: the message m is interpreted as an integer, then raised to exponent e, and the result is reduced modulo n. If e = 3 and m is short, then m3 could be an integer which is smaller than n, in which case the modulo operation is a no-operation. In that case, you can just compute the cube root of the value you have (cube root for plain integers, not modular cube root).


How to go about encrypting a digital exam?

Let's see if we can clear up some of the basic crypto concepts for you. (Though you should probably do a bunch more reading on your own, and maybe hire a crypto consultant if this system is more than just a course project. Sloppily done crypto can get an institution into big legal trouble.)

Public Key Encryption:

In public key encryption, you encrypt something with the recipient's public key, so that the recipient can decrypt it with their private key. Think of it like a mail slot in your front door: anybody can send you stuff by slipping it through the slot (ie encrypt with public key), but only the person who lives there can unlock the door and get it (ie decrypt with the private key). -- The idea of "encrypting with the private key of the sender" does not make any sense - you push it out the mail slot so anybody walking by your porch can look at it?

For your second question:

  2.Do I need a public and private key for every party the exam passes through? (lecturer, student, exam dept etc)

If you want all of those people to be able to read it, then yes, you will need to issue each of them keypairs and have a system like this:

Person A encrypts for person B --> Person B decrypts then re-encrypts for person C --> Person C decrypts then re-encrypts for person D --> etc

(Note that a scheme like this would be considered insecure in any other setting because any of those people could modify the exam before re-encrypting it, and there's no way to prove who changed it. So this likely isn't what you want either.)

System design:

In my opinion, the proper way to do this would be to assign every student a keypair - maybe attached to their user account? Or maybe every exam invigilator gets a keypair if that makes more sense. Then your central server encrypts N copies of the exam: one per student / invigilator. If there are intermediary people who need to see it (lecturer, dept, etc) then you make a copy encrypted for their keypair also. This way, once you encrypt a copy of the exam for Student X, then regardless of how many hands it passes through, only Student X will be able to open it. This is the type of usage that Public-Key encryption is designed for. (As a side note: this would work very well if each copy of the exam had a random number embedded in it so you know that Student X is handing in their copy of the exam, not their friend's copy.)

Edit:

Looking over your question again, the line

  Or do I just generate some kind of code that the recepient would compare it to? Is that what digital signing is?

doesn't fit with the rest of your question. Signatures are an anti-tamper system: they guarantee that this is the original document, and hasn't been modified, but does nothing to hide it (ie everybody can see the text).


I cannot understand the concept of a divisor for an elliptic curve

As @user94293 mentioned, divisors are a way to keep track of the zeroes and poles of a function. (Poles are related to projective coordinates).

Think of a function like $f(x) = x^2 - x + 6$. It has two zeroes: $-2$ and $3$. If I only gave you these two zeroes, you would be able to recreate the original function, up to a constant factor.

The reason divisors are used in pairing-based cryptography (and thus in ABE) is because the pairing function itself is defined as the function which has a particular divisor. This is enough since, as mentioned, if you have the divisor (and thus the zeroes), you can reconstruct the function.

In particular, the Tate pairing is defined as the function $\tau_r(P, Q) =  f_\tau(Q)^{(q^k-1)/r}$ where $f_\tau$ is a rational function (a function which is the ration of two functions) with divisor $r\langle P \rangle - r\langle \infty \rangle$, which means it has $r$ zeroes in point $P$ and $r$ poles in the point at infinity. This function is computed with Miller's algorithm.

In short, divisors are used to specify the pairing function used in pairing-based cryptography.


How can I find the generator of a composite group and $Z_p*$?

$\newcommand{\Z}{\mathbb{Z}}$If I have understood your question correctly, your goal is to find a primitive root modulo $p$, also called a generator of $(\Z/p\Z)^\times$, knowing that $p$ is prime.

Do you know the prime factorization of $\phi(p) = p - 1$?  If you don't, this is hard.  If you do, there's at least one common fast case, and there's always a general slow case.

Fast case.  Is $p$ a safe prime—that is, is there another prime $q$ such that $p = 2 q + 1$?  If so, then there are only four possible orders, $\{1,2,q,2q\}$, corresponding, respectively, to the subgroups $\{1\}$, $\{1, -1\}$, the quadratic residues, and the whole group.  Thus to find a generator of $(\Z/p\Z)^\times$ it suffices to find a quadratic nonresidue other than $-1$.

You can use the law of quadratic reciprocity to quickly pick a generator.  For example, if $p \equiv 3 \pmod 8$ or $p = 5$, then $2$ is a quadratic nonresidue and hence a generator; otherwise $p \equiv 7 \pmod 8$, since $p \equiv 3 \pmod 4$ by virtue of being a safe prime above 5, so $-2$ is a quadratic nonresidue and hence a generator.

(Why is this case common?  Often the goal is to find a generator for a Diffie–Hellman group, which over finite fields is always done with a safe prime modulus—although in that case usually one seeks a generator of the order-$q$ subgroup instead, i.e. a quadratic residue other than $-1$.  See, e.g., RFC 2412, Appendix E ‘The Well-Known Groups’.)
Otherwise, general case.  Let $\phi(p) = p - 1 = q_0^{e_0} q_1^{e_1} \cdots q_{k-1}^{e_{k-1}}$ for primes $q_i$.  March through the quadratic nonresidues $x \in (\Z/p\Z)^\times \setminus \{-1\}$, and for each distinct factor $q_i$ of $p - 1$, check whether $$x^{\phi(p)/q_i} \equiv 1 \pmod{p}.$$  If for some $x$ the powers $x^{\phi(p)/q_i}$ are all not congruent to 1 modulo $p$, then you have found an element of maximal order $\phi(p)$ which is therefore a generator.

(It doesn't hurt to test all elements, but you may be able to skip quadratic residues faster than computing the modular exponentiation.)


Proof of using a literal from known set, inside a computed formula

In Crypto 94, Cramer, Damgård and Schoenmakers proposed Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols with abstract below:
Suppose we are given a proof of knowledge $P$ in which a prover demonstrates that he knows a solution to a given problem instance. Suppose also that we have a secret sharing scheme $S$ on $n$ participants. Then under certain assumptions on $P$ and $S,$ we show how to transform $P$ into a witness indistinguishable protocol, in which the prover demonstrates knowledge of the solution to some subset of $n$ problem instances out of a collection of subsets defined by $S.$
For example, using a threshold scheme, the prover can show that he knows at least $d$ out of $n$ solutions without revealing which $d$ instances are involved. If the instances are independently generated, we get a witness hiding protocol, even if $P$ did not have this property.
Our results can be used to efficiently implement general forms of group oriented identification and signatures. Our transformation produces a protocol with the same number of rounds as $P$ and communication complexity $n$ times that of $P.$ Our results use no unproven complexity assumptions.
The authors also state:

Our techniques are to some extent related to those of De Santis et al. The models are quite different, however: They consider non-interactive proofs of membership, while we consider interactive proofs of knowledge.

The paper is available here


NIST test vectors for RSASSA-PKCS1-V1_5-SIGN with the SHA-256 hash function?

A zip file of test vectors (FIPS 186-2 Algoithm Test Vectors for RSA) can be found at the bottom of the page on NIST's site pertaining to CAVP Testing: Digital Signatures.

This file contains a readme and the test vectors for X9.31RSA,  RSA PKCS#1 Ver 1.5, and RSA PKCS#1 RSASSA-PSS signature generation. It looks like it does contain vectors for SHA-256.


Cryptosystems defined over the real numbers

The complex roots of unity form a finite group under multiplication

$$z^k = \exp\bigg(\frac{2k{\pi}i}{n}\bigg) = \cos\frac{2k{\pi}}{n} + i\sin\frac{2k{\pi}}{n},$$

where $z$ is a complex generator of the order-$n$ multiplicative group. This is a cyclic group and is isomorphic to any other cyclic group of the same order, for example the integers modulo 2 under addition, which is equivalent to Boolean XOR

$$a \oplus b \iff z^a z^b = z^{a+b}$$

This equivalence gives rise to the group Fourier transform, in which vector convolution in the complex domain correspond to point-wise multiplication in the additive group. This fact is used by Joan Daemen in his thesis to derive the DC/LC properties for the AES S-BOX.

The obvious practical problem with computing in this group is the error associated with floating-point arithmetic. As the number of arithmetic operations increases, so does the error. This kind of round-off error may be more appropriately called quantization noise in the signal processing context.


ECDSA signature generation and verification latency

I was expecting that the signature verification will be faster than the signature generation

Because signature verification is faster in RSA?  Well, as you can see, RSA != ECDSA; the operations involved in both signing and verification are completely different.

what makes the signature generation faster ?

Because signature generation involves only one point multiplication (plus a modular inverse; rather cheaper, but not of insignificant cost), while signature verification involves two point multiplcations.
Of course, if you dig beneath the textbook definition, there are available optimizations for both sides:
On the signature side:

The point multiplication $k \times G$ (and I'll be using the notation on the Wikipedia page) uses a fixed (defined by the Elliptic Curve definition) point; there are a number of ways to speed this up considerably by precomputing takes based on $G$.

In addition, the expensive operations involved with the signing operation don't depend on the message being signed.  Hence, if your implementation has some idle time, it could pregenerate $k$ and $r$ values; when it gets the message, it can use those values to sign the message with quite low latency.

Also, a word of warning: if you were thinking of using the same $k, r$ values for signing multiple messages, don't go there - that will leak you private signing key.  You really need a fresh $k$ value selected randomly for each signed message.

On the verification side, the expensive operation is the computation $u_1 \times G + u_2 \times Q_A$

One could use the precomputed table to compute $u_1 \times G$ quickly; this means that the time to compute $u_2 \times Q_A$ is the bulk of the time (and if you know you'll be verifying with a specific public key $Q_A$ lots of times, you could precompute tables based on that - I haven't heard of anyone going to that effort, as you'd need to verify thousands of signatures from that one public key to make it worth while).

Alternatively, there is Shamir's trick, which is a computational method to compute $a \times P + b \times Q$ in not much more time than it takes to compute a single point multiplication.  However, you lose the speed up from a precomputed table.

However, neither of these ideas results in a verification method that is as fast as signing with precomputed tables.


What does it imply if in RSA pow(m, e, n) is same as the m

Not necessarily.  With the (not so strong) primes p=211 and q=311, we have n=65621.  Using e=157, I came up with the following messages that encrypt to themselves:

1
5908
5909
11197
11817
17105
17106
23013
23014
28922
36699
42607
42608
48515
48516
53804
54424
59712
59713
65620

Finding such a message with strong primes would be extremely difficult, but I can't think of a reason it couldn't occur.

At this point I don't have an explanation for the consecutive numbers in the list.


Encrypt-then-MAC when encrypting data in multiple blocks?

You can do either. Though make sure you tighten up how you do the first scheme.

In the first case you are going to have multiple tags, 1 for each chunk. In the latter, you will have a single tag. If you are downloading files that are approximately 1MB, I think #2 makes sense. If you are downloading files that are 1GB or 1TB, maybe #1 makes the most sense, as you can stop the download if one of the chunks is bad.


CBC-MAC length extension attack with IV simulation

It seems that all this discussion about the IV is just to confuse the reader. Ignore IV. You just have to do a simple length-extension attack on the CBC-MAC. Yes, one message is enough.


You can find the definition in RFC 5915.

It defines an ECPrivateKey object:

ECPrivateKey ::= SEQUENCE {
 version        INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
 privateKey     OCTET STRING,
 parameters [0] ECParameters {{ NamedCurve }} OPTIONAL,
 publicKey  [1] BIT STRING OPTIONAL
}

From Section 3:

  The fields of type ECPrivateKey have the following meanings:

  version specifies the syntax version number of the elliptic curve
    private key structure.  For this version of the document, it SHALL
    be set to ecPrivkeyVer1, which is of type INTEGER and whose value
    is one (1).
  privateKey is the private key.  It is an octet string of length
    ceiling $(\log_2(n)/8)$ (where $n$ is the order of the curve) obtained
    from the unsigned integer via the Integer-to-Octet-String-
    Primitive (I2OSP) defined in RFC3447.
  parameters specifies the elliptic curve domain parameters
    associated to the private key.  The type ECParameters is discussed
    in RFC5480.  As specified in RFC5480, only the namedCurve
    CHOICE is permitted.  namedCurve is an object identifier that
    fully identifies the required values for a particular set of
    elliptic curve domain parameters.  Though the ASN.1 indicates that
    the parameters field is OPTIONAL, implementations that conform to
    this document MUST always include the parameters field.
  publicKey contains the elliptic curve public key associated with
    the private key in question.  The format of the public key is
    specified in Section 2.2 of RFC5480.  Though the ASN.1 indicates
    publicKey is OPTIONAL, implementations that conform to this
    document SHOULD always include the publicKey field.  The publicKey
    field can be omitted when the public key has been distributed via
    another mechanism, which is beyond the scope of this document.
    Given the private key and the parameters, the public key can
    always be recomputed; this field exists as a convenience to the
    consumer.

As pointed out in the comments, OpenSSL actually uses a slightly different format, namely the SEC1 format found in SECG's SEC 1: Elliptic Curve Cryptography. From the description of the openssl ec command:

  -inform DER|PEM

  This specifies the input format. The DER option with a private key uses an ASN.1 DER encoded SEC1 private key.

However, as was also noted, the differences are small even if they are worth noting. From RFC 5915's Appendix B:

  This appendix lists the differences between this document and
    SECG1:

  This document uses the I2OSP routine defined in RFC3447 while
     SECG1 defines its own routine.  The two routines result in the
     same output.
  SECG1 constrains its parameters (i.e., the curves) to
     SECGCurveNames.  This document constrains the parameters to
     NamedCurve from RFC5480.
  This document requires parameters be present while SECG1 does
     not.
  This document specifies requirements for encoding rules while
     SECG1 did not.


Is AES-256 weaker than 192 and 128 bit versions?

AES is an algorithm which is split into several internal rounds, and each round needs a specific 128-bit subkey (and an extra subkey is needed at the end). In an ideal world, the 11/13/15 subkeys would be generated from a strong, cryptographically secure PRNG, itself seeded with "the" key.

However, this world is not ideal, and the subkeys are generated through a process called the key schedule, which is very fast but not a decent PRNG at all; it is meant to offer sufficient security in the very specific context of producing subkeys for the AES only. The key schedule of AES was already known to be somewhat weak in some ways, allowing some exploitable structure to leak from one subkey to another, and this means related-key attacks.

Related-key attacks are not a problem when the encryption algorithm is used for encryption, because they work only when the victim uses several distinct keys, such that the differences (bitwise XOR) between the keys are known to the attacker and follow a very definite pattern. This is not the kind of thing which often occurs in protocols where AES is used; correspondingly, resistance to related-key attacks was not a design criterion for the AES competition. Related-key attacks can be troublesome when we try to reuse the block cipher as a building block for something else, e.g. a hash function. In the formal land of academic cryptanalysis, related-key attacks still count as worthwhile results, despite their lack of applicability to most practical scenarios.

The key schedules for AES-128, AES-192 and AES-256 are necessarily distinct from each other, since they must work over master keys of distinct sizes and produce distinct numbers of subkeys. It turns out that the version of the key schedule for AES-128 seems quite stronger than the key schedule for AES-256 when considering resistance to related-key attacks. It is actually quite logical: to build a related-key attack, the cryptographer must have some fine control over the subkeys, preferably as independently from each other as possible. It seems natural that the longer the source master key, the more control over subkeys the cryptanalyst gets -- because the related-key attack model is a model where the attacker can somehow "choose" the keys (or at least the differences between the keys). In the extreme case of a 1408-bit master key which would simply be split into eleven 128-bit keys, the cryptanalyst would have all the independent control he could wish for. Therefore, an academic weakness relatively to related-key attacks should, generically, increase with the key size.

The apparent paradox of the decrease in academic security when the key size increases highlights the contrived nature of the related-key attack model.


Is a collision attack possible on MD5 if message is known partially

If you have $\operatorname{MD5}(m_1||m_2)$ and you know $m_2$, and want to find $m'$ such that $\operatorname{MD5}(m'||m_2)$ reaches a known, predetermined value, then you must break MD5's preimage resistance, or at least second-preimage resistance.

This would be true even if you knew $m_1$: if you know $m_1$, then the problem becomes: find $m'$ such that $\operatorname{MD5}(m'||x) = y$ for two given values of $x$ and $y$ ($x = m_1$ and $y = \operatorname{MD5}(m'||m_2))$ in your presentation). Since $y$ is the result of MD5 on a known entry, this problem is a second-preimage attack with an extra constraint on the result. MD5 is still quite robust against second-preimage attacks, so this cannot be done with existing knowledge and technology.

Not knowing $m_1$ cannot help: if the problem is already hard with knowledge of $m_1$, then it cannot be easier without knowledge of $m_1$.

The explanation above is the general case. In some cases it can be quite easy: for instance, if $m_2$ happens to be equal to $z||m_1$ for some value $z$, then $m' = m_1||z$ would be a solution.

If you have $\operatorname{MD5}(m_1||m_2)$ and you know $m_2$, then you can trivially compute $\operatorname{MD5}(m_1||m')$ for any $m'$ which begins with $m_2$, followed by the MD padding, followed by arbitrary contents. This requires knowledge of the length of $m_1$ (but not its contents). For details, look up the length extension attack.


Deterministic encryption for a limited space: using HMAC as IV

Let L be your constant data length, choose a non-negative integer $\sigma$, choose a

FPE scheme over strings of length $\sigma$+L, and have $s$ range over strings of length $\sigma$.

encrypt$\hspace{-0.02 in}\big(\hspace{-0.04 in}\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle ,\hspace{-0.02 in}m\hspace{-0.03 in}\big) \;\;\;\; = \;\;\;\; $ FPenc (  k  ,  s || m  )

Decryption of c with $\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle$ is as follows:

if  length(c) ≠ $\sigma$+L  then output $\bot$, else set  d = FPdec(k,c)

if the left $\sigma$ bits of d are s then output the right L bits of d, else output $\bot$

Security should hold even if the adversary chooses $s$; you making it part of the key (in particular, random and secret) might reduce the impact of an attack on the underlying FPE scheme.

Depending on your use-case, you may be able to support a tweak.  The right FPE scheme depends on how 2$^{\sigma+L}$ compares to your upper bound the number of distinct [queries which are not just the opposite direction to an earlier query] (for any single tweak, if applicable).

The  low-query , medium-query , high-query  regimes are handled by

Generalized Feistel , swap-or-not , sometimes-recurse shuffle  respectively.

(I don't know whether-or-not they mention tweakability, but there's a simple generic

way to make any encryption scheme tweakable, which I can describe if you'd like.)

The main reason for using FPE rather than just a MAC is that

it essentially removes the adversary's control over the effects

of a successful forgery (thus perhaps allowing a shorter tag).

For example, with AES-CTR on a known plaintext, the adversary can

choose exactly what the decryption result will be if they guess the right tag.

A much-less-important reason is that forgery probability is in

fact slightly lower, since the guesses are nearly-independent.

Should I formalize either of those things?

If your scheme can be stateful, then you can further make it so that after any

attempted altering of what's sent (whether it's a replay or a re-ordering or just

a fresh cipher-block, and whether-or-not the attempt succeeds at forging),

[decryptions after the decryption of the initial tampering]

are indistinguishable from being independent with

$\big[\big[$probability  $1\hspace{-0.05 in}-\hspace{-0.03 in}\left(1/\hspace{-0.03 in}\left(2^{\sigma}\right)\right)$  of outputting $\bot \big]$    and

$\big[$probability $1/\hspace{-0.03 in}\left(2^{\sigma}\right)$ of outputting a random L-bit string$\big]\big]$ .

Should I explain how to do that?


Privacy and warrants to obtain information

Your warrant just needs a simple digital signature, which provides the properties of authenticity and non-repudiation. That is very basic. Of course you need a proper public key infrastructure (PKI) along that, to ensure that everyone actually knows which verification keys are real, etc.

Regarding your different authorization levels, you might want to look into Mandatory Access Control, which then needs to be fulfilled by the PKI. But instead of granting access, you use it to decide which certificates are signed within the hierarchy. I guess you are looking for a compliance solution here, not a fancy technical solution, which might not have a mature implementation.

In general, this question is actually not about cryptography (at most about the application of cryptographic standards) and might be better suited for security-SE.


Not only is $\mathbb G_1 = \mathbb G_2 = \mathbb G_T = \mathbb Z_p$ with $e(x,y) = x \cdot y \pmod{p}$ an example of a "bilinear group" (a triple of groups with a bilinear map) but every bilinear group of prime order is isomorphic to one of this form. So anything you want to know in principle about such groups, you can calculate on this example. I've used it myself before now as a sanity-check for some protocols.

The security of e.g. ECC implementations of bilinear groups rests on the fact that the isomorphisms to the $\mathbb Z_p$ form are not (thought to be) efficiently computable.

Of course it's cryptographically useless --- discrete logs are easy, as commenters have pointed out. But cryptographic definitions usually come in two parts, functionality and security. An encryption scheme for example is a triple (KeyGen, Enc, Dec) with a correctness property; the scheme where Enc and Dec are the identity maps is therefore an encryption scheme. Only when we introduce security requirements in a second step does this scheme turn out to be lacking. The same goes for $\mathbb Z_p$: it certainly is a "bilinear group" but not a particularly secure one.

EDIT: to answer your last question whether one can define other bilinear maps over $(\mathbb Z_p, +) \times (\mathbb Z_p, +)$: note that $1$ is a generator of $\mathbb Z_p$ so $e(x,y)$ is completely determined for all $x,y$ by $e(1,1)$. If you want a non-degenerate bilinear map, $e(1,1)$ has to be a generator of $\mathbb G_T = \mathbb Z_p$ too, and whichever generator you pick, the structures that you get are isomorphic. If you drop the non-degeneracy requirement, the map that sends everything to $0$ is a different, trivially bilinear one.


Does including the size of the hashed data improve security over just the hash

First the obvious; checking $M_L=D_L$:

is unnecessary from a security standpoint IF $H$ really is secure, by definition of that; but who knows what's really secure?
can't harm preimage resistance (first or/and second), nor collision resistance;
can greatly increase speed, if the hash is computed only after checking $M_L=D_L$; that's a common reason to perform this test in file de-duplication;
can harm the conceivable objective of hiding $D_L$ in some attack scenarios (such as timing or other side-channel attack);
harms even so slightly a common objective: simplicity.

It is possible to construct a devious $H$ that is collision resistant and second preimage resistant only if it is also checked $M_L=D_L$; e.g., a variant of SHA-256 that matches the original for messages of length $l\ge255$ bits; and for shorter messages outputs the original message, a one bit, and $255-l$ zero bit(s). That can be improved to a hash that is very secure from the standpoint of second preimage resistance if $M_L=D_L$ is checked, and less secure (according to some parameter) otherwise. That's indicative checking $M_L=D_L$ could help security for some otherwise insecure hashes.

If we take MD5 as an example: we know how to create collisions with little effort (including for messages with different and arbitrary beginning), but that's only if these messages have exactly the same length. Otherwise, the best known attack is brute force (feasible, but never performed publicly as of today for being too expensive). However that applies to collision-resistance, not to the question's preimage resistance (neither first nor second). Thus, in the case of MD5, we know that adding a check that $M_L=D_L$ does not significantly improves collision resistance, but MD5 remains preimage resistant without that check.

Definitions used:

first preimage resistance: given some arbitrary value the size of a hash, it is difficult to find a message with that hash.
second preimage resistance: given some arbitrary message, it is difficult to find a different message with the same hash.
collision resistance: it is difficult to find two distinct messages with the same hash.


Least-weak way to authenticate using only AES ECB/CBC

Is there any worthwhile way to authenticate the message using only
  these functions and simple checksums?

As usual, of course there is: AES-CCM!

AES-CCM basically is CTR mode with a tagged-on CBC-MAC and length prepending. You can implement CTR trivially using your ECB primitive and CBC-MAC shouldn't be too hard to implement given a CBC primitive and direct function access.
If implementig CTR is infeasible, CBC should do the job just as well.
If you want to go fancy (and don't live with length-prepending) you can also go for AES-EAX although it's a bit more difficult to implement.

  If I just did something like a 32 bit checksum of the plaintext and
  appended it before encryption, would that be vulnerable to attack
  (other than being only 32 bits of protection)?

No, this is a bad idea. Not only is a checksum usually not safe in the sense that a proper cryptographic hash would be, but also is this composition already insecure as fgrieu explained much better than I ever could in his answer to "Why is plain-hash-then-encrypt not a secure MAC?".

Relevant standards: CCM: RFC 3610, NIST SP 800-38C (PDF); EAX: The original specification


Deterministic Key using a seed for ECNamedCurve

The problem is that this requires relatively low level access to the cryptographic algorithms.
In general the private key can simply be set to a set of bits, although it should actually fit in the field. Setting the highest bit to zero is a dirty trick if the runtime(s) do not accept as many random bits as the key size. This will however let you use any kind of KDF to derive the bits.
The public key is nothing more than the private key S multiplied with the generator point. This is where you may get in trouble, as this operation is a low level function that may not be exposed.
In principle you could use ECDH for this using the generator as public point of the "other party", but the Java API is high enough that it won't directly return the resulting point, making this a useless exercise (other API's may differ though, so I thought I should mention this).
So in general you'll need a low level API to perform functions like that.

In your case the best way forward is to use the Bouncy Castle libraries, where such low level functionality is supplied by the lightweight cryptography API. Bouncy Castle also has a nice set of KDF's that you can use. I know 'cause I did the initial implementation.


I guess, you are referring to the mix columns operation from the point of view with polynomials over $GF(2^8)$.

A detailed explanation of this can be found at Wikipedia. It is a quite unusual structure, but it behaves just like you would consider any $GF$.

The columns are first considered as polynomial, or better: as coefficients for a polynomial of degree 3.
Then this polynomial is multiplied with a constant polynomial ($3x^3+x^2+x+2$)
Addition in this field is done with the XOR operation
Multiplication is quite complex, for details check out this.

As for your questions:
There are two different modulo operations. One is considered on the $GF(2^8)$, which is $100011011$. But this is just the finite field for the coefficients, and in the overall structure you actually deal with polynomials modulo $x^4+1$. I guess you have an error in your actual number there, because if you just write the hexademcimal representation of the coefficients, that would be the coefficients $1,0,0,1$ (with coefficients from 0 to 255), or $1|00|00|01$ written in hexadecimal.


Can someone steal the key between 2 clients which are using Symmetric Encryption?

In this answer I shall assume that the two relevant parties already share a strong symmetric key (ie not a password), which may have been established by e.g. using appropriate key agreement techniques (such as those used by TLS which may use asymmetric cryptography) or by e.g. physical, secure courier transport.

No, an attacker cannot learn the key or anything about the messages except their lengths if an appropriate (set of) encryption mechanism is used. In these protocols, the symmetric key is usually used to derive encryption and authentication keys and these are used to encrypt and authenticate messages between the parties. Man-in-the-middle attacks are then thwarted by the security of the symmetric-key encryption schemes as well as by the fact that the other party is authenticated by knowledge of the relevant symmetric key.

Additionally, sometimes the symmetric key is combined with the result of a run of the Diffie-Hellman protocol to gain extra security properties such as that when the symmetric key is leaked in the future, no past sessions can be decrypted.

One example set of protocols, that achieves these security properties given a shared symmetric key is the PSK ciphersuites from TLS.


K-dimensional equidistribution - how big are periods of PCG?

PCG is just LCG where the output is run through a transformation. The amount of internal state of the PCG - which is what controls the period - is all contained in the underlying LCG. So the period is $2^n$ where $n$ is the number of bits of state. The only thing to worry about is if the output transformation makes the period smaller, but since it's a permutation it does not.
When pcg-random.com talks about "arbitrary" period, they just mean that they have a way to make the internal state arbitrarily large. For a given state size, the period is the same as other algorithms of the same size.


In RSA $(e,n)$, $(d,p,q)$, why does it work even if plaintext $M$ is not coprime with $n$?

By construction, we have $ed\equiv 1\pmod{\lambda(n)}$, hence $ed\equiv1\pmod{\lambda(n)}$ since $\lambda(p)=p-1$ divides $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Fermat's little theorem thus implies that $(M^e)^d-M\equiv M^{ed}-M\equiv0\pmod p$ for any $M\in\mathbb Z$.


Are there any benefits to using ECB over CBC?

ECB benefits:

It's a tiny bit easier to implement.
It allows for parallel encryption and decryption (CBC only decryption).
A single corrupted cipher block corrupts only one block of plain text(in CBC it is 2)
It doesn't need an IV

ECB downsides:

In almost all cases it is insecure.

For comparison, CTR mode allows parallel encryption and decryption and a single corrupted bit corrupts only 1 bit (not even a whole block as in ECB). Also CTR doesn't need padding or have padding related weaknesses.

If you have high entropy messages where message blocks never repeat ever then ECB could be acceptable, but it's just asking for trouble.


The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).

But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.


Should you change salt when changing password?

If the attacker had already begun creating a rainbow table or is engaged in some other attack which requires knowledge of the salt, then a password change with a salt change will require the attacker to start from scratch.

Always assume the attacker has before and after copies of the password hash and salt.

If the salt is not changed, any work the attacker has done may still be applicable to the new password. It may even mean the new password is already in the rainbow table or has been cracked in some other way.


I read that two-round Feistel network is not a secure PRP

That's easily seen:

It holds $P_L\oplus C_L=F_0(P_R)$. That implies a distinguishable property: for any fixed $P_R$ and whatever the round function $F_0$, when we flip bit(s) in $P_L$, that flips the corresponding bit(s) in $C_L$ and leaves the other bit(s) in $C_L$ unchanged.
That property allows a break under Chosen Plaintext Attack.


Do deterministic secret sharing schemes exist?

Any deterministic secret sharing scheme as in the question has the property that any participant can run the deterministic algorithm for a guess of the shared secret, and eliminate the guess if the share that the algorithm deterministically assigns him/her does not match his/her share. This implies that some information about the secret is leaked in his/her share, or that his/her share is pointless (in the sense that his/her share can be removed from any set of shares that allows to reconstruct the secret, while keeping that ability).

Likely that's why there is no seldom such beast in the literature. For a counterexample to this assertion, see that other answer.


E0, being based on LFSRs, is not a particularly secure stream cipher. The key can be recovered via a known-plaintext attack given enough plaintexts. Two-level E0, which uses the keystream of one E0 instance to initialize the state of a second instance which itself encrypts only one 2745-bit frame, is vulnerable to an attack requiring 238 simple operations given the initial 24 bits of 223.8 frames. This is practical against Bluetooth even using two-level E0 for confidentiality. Note that one-level E0, which simply uses E0 directly as a stream cipher, is even more vulnerable to known-plaintext attacks.

To answer your questions directly:

E0 is not secure, even when used in the so-called two-level E0 scheme.
Known-plaintext attacks can be used to recover the key in negligible time.

If you need an extremely lightweight stream cipher, consider using ChaCha8, which is capable of encryption at the rate of 1.88 cycles per byte on a Core2Duo. Heavy optimizations may improve the keystream generation rate even more. ChaCha is an ARX cipher, using only addition, rotation, and bitwise exclusive-OR. The most secure shift register-based stream cipher out there, which is even faster, is Trivium, which takes only 80-bit keys. I'd recommend against it, but it is still better than E0.


Quantum algorithm encrypting classical data

Yes, a quantum computer can implement any classical algorithm.

This can be easily proven, because quantum computers are Turing-complete. And if a computer is Turing complete then it can, by definition, run any classical algorithm:

  A universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer.

And that's - as far as I can see - QED.


How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?

This partial answer establishes (rather trivial) lower and upper bounds for the asymptotic hardness of the problem, assuming $h$ behaves like an $n$-bit wide random function.
If one hashes $m$ messages $M$, then computes $f(i,j,k)=h(M_i)\oplus h(M_j)\oplus h(M_k)$ for $(i,j,k)\in\mathbb {Z_m}^3$, that's $m^3$ results, with most values duplicated at least 6 times for large $m$. Odds that zero is never reached by any $f(i,j,k)$ are about $(1-2^{-n})^{m^3/6}$ for large $m$, for any choice of the $M$ by an adversary who can't distinguish $h$ from a random function.
Therefore, if $m\approx2^{n/3}$ hashes have been computed, that can not lead to a solution of the problem with odds better than 16% for large parameters.
The expected hardness of the problem in the question is thus at least $\mathcal O(2^{n/3})$ times the work for a hash. Also, an infinitely powerful adversary could succeed with $\mathcal O(2^{n/3})$ queries to an oracle implementing the hash.

The above leads to an explicit algorithm with non-vanishing odds of success that performs $(2^{n/3})^3=2^n$ evaluations of $f$, thus has cost $\mathcal O(2^n)$ $n$-bit operations; it requires $\mathcal O(2^{n/3})$ $n$-bit words of memory. We can do much better.
One option is to fix $a$, then find collisions for the function
$$g(x)=\begin{cases}h(x) & \text{if }x\text{ is even}\\h(x)\oplus h(a) & \text{if }x\text{ is odd}\end{cases}$$
This search can be can be made with cost $\mathcal O(2^{n/2})$ hashes and modest memory, using Floyd's cycle-finding, or Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).
Notice that if $g(b)=g(c)$ with $b\ne c$, then $(a,b,c)$ is a solution of the problem of the question if $b$ and $c$ have different parity, which (for random $h$) has odds about $1/2$ for each collision exhibited.
The expected hardness of the problem in the question is thus at most $\mathcal O(2^{n/2})$ times the work for a hash.


My solution is based on Pedersen commitments; in this scheme, we work in a prime-sized ($p$) subfield of some group, perhaps $\mathbb{Z}_{kp+1}$, so some prime $kp+1$; where both $p$ and $kp+1$ are large enough to make the discrete log problem intractible.  We have two generators of this subgroup $g$ and $h$, and it is important that no one knows the discrete log of $h$ base $g$.

A commitment in this scheme to a value $x_i$ is the value $g^{x_i} h^{r_i}$ for a random value $r_i$; if you want to open the commitment, you reveal $x_i, r_i$.

One of the things that is interesting about this scheme is that it makes it easy to prove linear relationships; for example, if we have committed to $n$ $x_i$ values, issuing the commitments $c_i = g^{x_i} h^{r_i}$, and want to issue a proof that $\sum a_i x_i = b$ for some public constants $a$ and $b$, all we need to do is to proof that we know the value $y$ such that $\prod (c_i)^{a_i}\cdot g^{-b} = h^y$ - the left side can be computed by the verifier, and so a simple Schnorr proof suffices (and, assuming that the prover remembers all the $r_i$ values he used, he can easily compute $y$)

And, I'll assume that the polynomials $B(x), D(x)$ have a known maximum degree $n$; the polynomials $A(x), A'(x)$ have a known maximum degree $m$ (which may be larger).

With this tool in our toolbox (and with the above assumption), it becomes easy.  To commit to $A(x)$, you publish Pedersen commitments to each coefficient individually (and similarly with $A'(x)$ - there is no need to use the same $r_i$ values unless you decide to make the relationship between $A(x), A'(x)$ obvious at the start)

Then, to send $C(x)$ to X (along with a proof that $C(x) = A(x) \bmod B(x)$), well, we have $A(x) = B(x)K(x) + C(x)$ for some polynomial $K(x)$; so you would give $m-n+1$ Pedersen commitments for the coefficients of $K$.  Then, the above equation can be viewed as a series of linear equations between $A(x)$ and $K(x)$ (and the public to X polynomials $B(x), C(x)$.  So, we just issue $m+1$ proofs that each individual coefficient of $B(x)K(x) + C(x)$ matches $A(x)$.

The last step is to issue a proof that $A(x) = A'(x)$; that is easily done, as that is just another linear relationship, and so the same tool can do it.

QED


Since we're talking about classical cipher, I'll assume an alphabet will be the dataset we're working with; thusly, a letter from the alphabet will be a datum from the dataset.
A permutation defines the process that maps letters to possibly different letters. Two friends can agree on a single such permutation to exchange secret information.
If we want the encryption algorithm to be useful, different groups of people should be able to easily obtain different permutation by choosing a key.
However, if a different key can select the same permutation, then that key breaks the secrecy of the first key. Even worse, if a group of keys yields same (or even similar) permutation, then decrypting other messages encrypted using other keys in the group of keys becomes very easy. And this is very bad for an encryption algorithm.
Update for OP's comment
The above text discusses a "hypothetical" cipher (not Vigenere or any specific cipher) with weak keys, and explain some reason why it can be bad (it is bad regardless of what cipher we're talking about).


What is the difference between regular and "twisted" ECC curves?

TL;DR: There is no difference.

Given an elliptic curve $E$ defined over $\mathbb{F}_p$ for some prime $p$, we say that a second curve $E_t$ defined over $\mathbb{F}_p$ is a twist of $E$ when $E_t\cong E$. That is, when there is an isomorphism between $E_t$ and $E$, defined over $\bar{\mathbb{F}}_p$ (the algebraic closure of $\mathbb{F}_p$).

From this we can conclude that every curve is a twisted curve, as every curve is isomorphic to itself. Thus the definition of a regular curve versus a twisted curve is nonsensical, there is no difference.

You may be left wondering why we care about twists in the first place. Well, it turns out that given some curve $E/\mathbb{F}_p$, in some cases one can force a user to work on some twist of $E$ instead (there could be many twists). This twist could have different security properties (notice the definition of twist with respect to $E$), which could in turn lead to an attack. This is an example of a so-called invalid-curve attack.

Edit: Note that ${\tt brainpoolPXXXr1}$ and ${\tt brainpoolPXXXt1}$ are trivial twists (see Definition 9.5.1). That means that the security properties are essentially the same. The reason why both these curves are specified, is because ${\tt brainpoolPXXXr1}$ is pseudo-randomly generated (and therefore supposedly leaving them unable to create backdoors), yet has large curve parameters. By specifying ${\tt brainpoolPXXXt1}$ which has $A=-3$, we can make some improvements in the curve arithmetic, making operations more efficient (see EFD).


Is there a perpetual 2-factor-authentication scheme that allows temporary password generation?

If you use asymmetric cryptography you can make it work. The trusted device stores a private key and salt the user will type his password and it will get hashed with salt and get encrypted/signed and the result sent to server which has public key and the salted hashed password. The main problem is the trusted device now sends something much larger then the common short tokens used today. Also public key crypto is more computationally expensive, we know how to make the server side cheap but not both sides.
A server breach doesn't expose the private key, a trusted device breach doesn't expose the password and a loss of password doesn't expose the private key.


Why does CBC decryption with a wrong IV still give readable results?

This is what ciphertext block chaining is about - each plaintext block is XORed ("chained") with the previous ciphertext block before encrypting (and after decrypting).

The initialization vector then takes the place of the ciphertext block before the first block (since there is none).

So, mistaking the initialization vector as a ciphertext block does nothing wrong for decryption (other than that you'll get an additional garbage block of plaintext).

You did observe (part of) the malleability property of CBC: One can change the start of the ciphertext (including the IV), even prepend/remove blocks, and the result is still a valid ciphertext, and the plaintext block after the changed one will be changed in a predictable way.

This is used for some attacks on protocols using CBC, when they allow a chosen-ciphertext attack - search for the padding oracle attack, for example.
For this reason, you always (not only for CBC) should use authentication together with your encryption, for example in form of a MAC around your ciphertext (including the IV).


Concatenation of two strong hashes may have striking weakness

If we use $H_1(X) = H_0(X) \oplus firstnbits(X)$, this would seem to be trivial.

EDIT: As Cédric Van Rompay pointed out, this is only a counterexample if $H_1$ winds up being preimage-resistant. This may not be a necessary consequence of $H_0$ being preimage-resistant, but I really only need one case where it is.


The relevant mathematics is elementary linear algebra.

Focusing on the relevant part of the problem, the defender calculates a signature
$$S(m_1, \ldots, m_n) = H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n)$$
where $\oplus$ is bitwise xor, $H$ is a cryptographic hash function and $(m_i)$ is a family of messages (which are file names) of variable size. The goal of the attacker is to find a family of messages such that:

The signature is equal to some value $S_o$ which is the signature of the legitimate message.
One of the messages has a specific content which is the payload that the attacker wants to inject.
No two messages can be equal, because there can only be a single file by a given name.

So we need to find $n$ and $m_1, \ldots, m_n$ such that
$$S_0 = H(m_0) \oplus H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n)$$
i.e.
$$H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n) = S_1$$
where $S_1 = S_0 \oplus H(m_0)$.

If $H$ was invertible, we'd just take $n=1$ and $m_1 = H^{-1}(S_1)$. But since $H$ is a cryptographic hash function, this approach is out. Nonetheless, let's look a bit more at what we could do if we could find messages whose hash has a specific value.

$H(m)$ is a 256-bit value. Suppose we could find 256 messages $(M_1,\ldots,M_{256})$ such that $H(M_i)$ is all-bit-zero except that the $i$th bit is set. Then we could take a subset of these messages corresponding to the bits that are set in $S_1$: $S_1 = \bigoplus_{i \mid \text{the \(i\)th bit of \(S_1\) is set}} H(M_i)$.

We're trying to express $S_1$ as the xor of a bunch of values. The xor operator is linear: it satisfies all the axioms that define a vector space over the field $GF(2) = \mathbb{Z}/2\mathbb{Z}$. In the field $GF(2)$, the elements are $0$ and $1$, the addition $\oplus$ satisfies $1 \oplus 1 = 0$ (i.e. it's xor) and three's only one way to define multiplication ($0$ times anything has to be $0$ and $1$ times anything has to be that thing). Bitwise xor on 256-bit numbers is vector addition in the vector space $GF(2)^{256}$. And expressing a vector as the result of adding a bunch of vectors is a well-studied problem: we're trying to express $S_1$ as a linear combination of some values.

Any value can be expressed as a linear combination of $100\ldots0$, $0100\ldots0$, $00100\ldots0$, …, $0\ldots010\ldots0$, …, $0\ldots01$. Picking the bits that are set in the resulting value means taking each term $0$ times if the corresponding bit in the result is clear and $1$ times if the corresponding bit is set. A set of vectors such that any value can be expressed as a linear combination is called a generator set of the vector space. A set of vectors such that none of them is a linear combination of the others is called linearly independent. A linearly independent generator is called a basis of the vector space.

If a vector space has a finite basis, then all of its bases have the same number of elements. This number is called the dimension of the vector space. Here we're working in a vector space with a 256-element basis, so it's a 256-dimensional space. The dimension has other nice properties, including the fact that in a vector space of dimension $d$, if a set of $d$ vectors is a generator then it's a basis, and if a set of $d$ vectors is linearly independent then it's a basis.

Recall that our problem is to find a way to express $S_1$ as a linear combination of some vectors. Furthermore each vector must be the hash of some message. We can do that by:

Finding a basis made of vectors that are the hashes of known messages.
Expressing $S_1$ as a linear combination of this basis.

For part 1, recall that it is enough to find 256 hashes that are linearly independent: since the vector space has dimension 256, such a set of 256 hashes will be a basis. $H$ is a cryptographic hash function, so it behaves essentially at random. We can take any message, calculate its hash, and if we don't like the resulting hash then we take a different message and try again. We can construct 256 successive messages such that each new message's hash is not a linear combination of the previous ones. That is:

Take an arbitrary $m_1$. While $H(m_1) = 0$, change $m_1$ and try again.
Take an arbitrary $m_2$. While $H(m_2)$ is either $0$ or $H(m_1)$, change $m_2$ and try again.
Take an arbitrary $m_3$. While $H(m_3)$ is a linear combination of $\{H(m_1),H(m_2)\}$, change $m_3$ and try again.
Take an arbitrary $m_4$, etc.

After building $k$ messages $(m_1,\ldots,m_k)$, there are $2^k$ hashes that are linear combinations of the hashes of those messages. This means that the number of forbidden hash values at each step is $2^0$, $2^1$, $2^2$, etc. At the 256th and last step (i.e. after building 255 messages), the number of forbidden hash values is $2^{255}$, which is half of the total number of possible hash values. This means that the probability of a successful draw is $1/2 = 1-1/2$ for each attempt at the last stage, $1-1/4$ at the previous stage, $1-1/8$ at the stage before, etc. Note that the probability of success is always at least one half, so this randomized algorithm is practical, it won't get stuck trying to find something that's almost impossible to find.

Part 2 is a classical problem in linear algebra which led to the definition of multiplication of matrices. We saw above how to express any vector as a linear combination in the basis made from vectors with all-bits-zero-except-one. We now want to express the old basis in terms of the new one, i.e. to express each all-bits-zero-except-one vector as a linear combination of the new basis. This means finding the inverse of the matrix that expresses the new basis in terms of the old one, which is equivalent to solving a system of 256 linear equations (one for each bit position) with 256 unknowns (the coefficient of each vector in the basis).


Equal hashes for different messages when doing key length extension attack sha1

Is this the normal behaviour?

No, it is not.  While it is known that SHA-1 collisions can be found, it's a lot more work than what you do.

It's likely to be a bug in your code.  I went through your code, and I'm not sure whether you might be computing the hash of the same preimage each iteration - that would certainly cause each hash to be the same.


Finding scalar that creates a point with zero X-coordinate for popular elliptic curves

No (See 2.). An alternative way to test a library could be to change the base point. You can find the point with x coordinate equal to zero, multiply it by a random $r$ and then use the result as the base point of ECDSA with $k=r^{-1}$.
This is equivalent to solving an ECDLP (discrete logarithm problem) which on standard curves, is believed to be hard (practically unfeasible)
This is possible.
$s=k^{-1}(z+rd)$ which is 0 when $(z+rd)=0$. If you can freely choose $z$ (e.g. the library receives it as parameter, and doesn't compute it internally) then you can choose $z$ such that $z=-rd$. Otherwise, you can select $d$ such that $d=-\frac{z}{r}$.

Note that another corner case that I test on implementations of ECDSA is where the $x$ coordinate of $k*G$ is greater than the $G$'s order. This again is done with the same trick I described in point 1.


Doesn't d6 to binary for 256-bit bitcoin private key generation produce biased results?

Yes, the method you describe above would indeed produce a key with only about $\frac{256}{3} \cdot \log_2 6 \approx 220.6$ bits of entropy.  (I say "about" because 256 is not divisible by 3, so the last die roll will only contribute one bit to the key, and the amount of entropy that bit will have depends on which of the three bits you choose.)

However, that's not what the script suggested on the page you linked to actually does.  Rather, it takes 100 rolls of a six-sided die (with a total entropy of $100 \cdot \log_2 6 \approx 258.5$ bits), interprets them as a base-6 number (after shifting the digits 1–6 to the range 0–5) between $0$ and $6^{100}-1$, and then converts this number to hexadecimal and takes the last 64 hex digits of it (which is equivalent to reducing it modulo $16^{64} = 2^{256}$).

This method will yield a key with almost 256 bits of entropy.  The reason it's only almost is because $6^{100}$ is not evenly divisible by $2^{256}$, so the modular reduction will introduce some bias.  In particular, $6^{100} \mathbin/ 2^{256} \approx 5.64$, so the lower 64% of the range of possible keys will be 6 / 5 times as likely to be chosen as the upper 36%.  Thus, the actual entropy of a key generated by this method will be approximately $$0.64 \cdot 2^{256} \cdot \tfrac{6}{6^{100}} \log_2 \left( \tfrac{6^{100}}{6} \right) + 0.36 \cdot 2^{256} \cdot \tfrac{5}{6^{100}} \log_2 \left( \tfrac{6^{100}}{5} \right) \approx 255.995 \text{ bits}.$$

BTW, simply rolling the die 99 times to generate a number between 0 and $6^{99} \approx 2^{255.91}$ and using that number directly as the key would yield a key with 255.91 bits of entropy, only about 0.08 bits less than the method used by the script.  Just to explicitly state the obvious, such differences of a fraction of a bit are completely insignificant — for all practical purposes, both methods will produce keys that are as good as a perfectly random 256-bit key would be.

In any case, even a key with 220 bits of entropy, as generated by the method described in your question above, should still be perfectly adequate for resisting brute force guessing attacks by any known or foreseeable adversary (at least using classical computers — but then, if large-scale quantum computing ever takes off, it will be bad news for elliptic-curve crypto regardless of key size anyway).

If you're worried about the special structure of the key (i.e. the avoidance of two digits out of eight when written in octal) possibly enabling some unknown class of attacks, just feed it through a hash function like SHA-256 before using it.  For that matter, you might as well just take a series of 100+ six-sided die rolls and feed it through SHA-256 to get a key that's effectively indistinguishable (assuming that SHA-256 is secure) from a perfectly random one.


Turns out that this was an open question. Brakerski et al. [BDGM] posted a paper today on the ePrint claiming the first (provable) post-quantum construction of iO. Their underlying security assumption is the "circular security" of an encryption scheme based on LWE.
[BDGM], Brakerski, Döttling, Garg and Malavolta, Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices, ePrint Archive


Homomorphic Encryption Arithmetic Operations

The way to solve the problem in the question is to change the question slightly (beyond changing "Psuedo" to pseudo-code).

What really is wanted most likely  is

A public-private key pair generation method
An encryption function $E$; accepting as input any integer in $\mathbb Z_N$ (the plaintext), a public key generated as above, and a random number; producing as output an integer in $\mathbb Z_R$ (the ciphertext); so that knowledge of the ciphertext without the private key and the random number essentially won't reveal anything about the plaintext (with the possible exception of negligibly few plaintext). We'll note encryption $E$ functionally, omitting both it's public-key and random inputs: $E(5)$ will thus be different from one invocation to the other, including for a fixed public-private key pair.
A decryption function $D$, accepting as an element of $\mathbb Z_R$ and the private key, with the property that for $\forall x\in\mathbb Z_N, D(E(x))=x$ (when the public and private keys match).
An operation $\boxplus$ on $\mathbb Z_R$, such that
$$\forall x\in\mathbb Z_N,\forall y\in\mathbb Z_N,\ \ x+y<N\implies D(E(x)\boxplus E(y))=x+y$$

Pallier encryption provides just that, with $R=N^2$ and $\boxplus$ defined as $u\boxplus v\ =\ u\cdot v\bmod R$.

Note: notation in this answer was adjusted to better match standard texts on Pailler encryption; refer to e.g. Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (2nd edition) section 13.2.


Is this the mathematical equation for the Vigenere Cipher

NO, the question does not contain the mathematical equation for the Vigenere Cipher with plaintext t and ciphertext c in thet set $\{1\dots 26\}$ (with the letter a as 1 and the letter z as 26), and displacement (or key) n, for two reasons:

the best interpretation I can make of the expression given is by considering -> to be the $\implies$ mathematical symbol, and ^ to mean logical XOR (or perhaps logical OR), that is one of the left thing or the right thing holds (possible meanings of the word one are equivalent in the context); but even with these assumptions, for n of 1 (meaning next character, circularly) the expression given maps the plaintext y (coded by t of 25) to the ciphertext a (coded by c of 1) instead of the desired z (coded 26);
the expression given does not parse (to me) as a mathematical equation.

With the original formalism, the Vigenere Cipher with plaintext t and ciphertext c in $\{1\dots 26\}$, and displacement n in the set $\{0\dots 26\}$, a correct expression would be:

((t + n) > 26 -> c = (t + n) - 26) ^ ((t + n) <= 26 -> c = (t + n))

and a passable mathematical equation would be:
$$t\mapsto c=((t+n+25)\bmod 26)+1$$

If we use the set $\{0\dots 25\}$ for plaintext and ciphertext, we get the nicer
$$t\mapsto c=(t+n)\bmod 26$$

or in the original formalism the expression

((t + n) > 25 -> c = (t + n) - 26) ^ ((t + n) <= 25 -> c = (t + n))


I am using chunks of 1MB and give them a GUID as filename

That is fine although unnecessary, the entire input file can be encrypted.

  These chunks are then first compresses using DEFLATE to minimize attacks based on known Content

VERY BAD idea, since you are breaking the input file into pieces, you are now exposing the entropy of specific file sections to an attacker. Either compress the file before you break it up, or do not break it up at all (or do not compress it)

  These chunks are then encrypted using Rijndael and a given Cipherkey. The IV will be created as an XOR of my Filename and the Key.

VERY BAD idea, now the attacker has the key. Use a random IV for CBC mode or a sequential IV for CTR mode. You have not specified your mode of operation.

  All chunks are then collected in an XML File, which is saved the same way but named as the original file name

I would keep the actual file name in the XML file in an encrypted format so you do not expose the potential file type or content. You can also keep hashes of the encrypted data, and integrity information in the XML file.

  Are there are other obvious weak spots that I am missing

Probably; your proposed IV generation scheme means you do not know enough about cryptography to be developing an encryption program, do more research and get more education on the subject before continuing. Cryptography Engineering would be a good starting point.


Encrypting small values with RSA private key

In any public key system, you don't encrypt with private key. You encrypt with public key, or sign with private key.

If your goal is signing (resp. encrypting) one small value with the RSA private (resp. public) key, keeping the signature small: forget about it, that's not directly possible. Under RSA, a cryptogram is always of size at least comparable to the key. You need another public key scheme. Edit: standard RSA signatures schemes have signatures about as wide as the public modulus; a state of the art RSA variant can about half that.

If you want to encrypt several small values with RSA, do that with a random secret key drawn for that purpose, and a symmetric cipher; and send the secret key, RSA-encrypted with the public key, using a proper padding scheme like OAEP.

If you want to sign several small values with RSA, concatenate them (each with length indication unless the lengths are agreed in advance), then sign the aggregate using a proper RSA signature scheme like PKCS#1 PSS. If you want to send the small values along and care about the total size, use a signature scheme with message recovery, such as ISO/IEC 9796-2 (but beware that the first of the three schemes in this standard, still the most used, has some flaws if the opponent can obtain the signature of enough chosen messages).


Converting a stream cipher into a block cipher

In an answer to another question, Zooko mentioned the BEAR and LION constructions,  linking to this paper: Two Practical and Provable Secure Block Ciphers: BEAR and LION.

These build a block cipher (with large blocks) from a stream cipher and a hash function (a keyed one (i.e. a MAC) for BEAR, a unkeyed one for LION).

The authors basically build block ciphers (with variable block sizes $m$) from a keyed hash function (a function family $H_K : \{0,1\}^* \to \{0,1\}^k$) or a normal hash (a function $H' \{0,1\}^* \to \{0,1\}^k$) and a stream cipher (a function $S : \{0,1\}^k \to \{0,1\}^n$, for arbitrary $n$ from context; here $n = m-k$).

These work by fist splitting the input block of size $m$ in two parts, one (L) of size $k$ and one (R) of size $m-k$, doing the encryption/decryption, and putting the two parts again together. We also have two keys $K_1$ and $K_2$, each of length $k$.

For BEAR, the encryption is done by

$$  L := L ⊕ H_{K_1}(R) $$
  $$  R := R ⊕ S(L)  $$
  $$  L := L ⊕ H_{K_2}(R) $$

and decryption the other way around:

$$  L := L ⊕ H_{K_2}(R) $$
  $$  R := R ⊕ S(L) $$
  $$  L := L ⊕ H_{K_1}(R) $$

For LION, we use a un-keyed hash function $H'$, and we have two calls of the stream cipher instead of the hash function instead of two keyed hash calls. Encryption:

$$  R := R ⊕ S(L ⊕ K_1) $$
  $$  L := L ⊕ H'(R) $$
  $$  R := R ⊕ S(L ⊕ K_2) $$

Decryption:

$$  R := R ⊕ S(L ⊕ K_2) $$
  $$  L := L ⊕ H'(R) $$
  $$  R := R ⊕ S(L ⊕ K_1) $$

E.g. decryption is in both cases just encryption with swapped key halves.

These are effectively Feistel networks with three asymmetric rounds.

The paper proves that these are secure (against certain attacks) as long as even one of the component functions is secure (e.g. breaking the composed primitive allows breaking both of the components).

There is a third construction mentioned in this paper, LIONESS, which uses four rounds (two keyed hashes, two stream cipher calls), which also provides resistance against an adaptive combined chosen plaintext and ciphertext attack.


How does Flatten really make the coefficients of a vector matrix small in LWE

The important part you missed is the last sentence of the first block:

$BitDecdomp^{-1}$ is still well-defined, if it doesn't get a $N$-dimensional bit vector (all entries from $\{0,1\}$).

In the second quote,  $Flatten$ is defined as first using $BitDecdomp^{-1}$, and then use $BitDecomp$. So the output of $Flatten$ will be a bit-vector. This will be the same as the input only if that input was also a vector from $\{0,1\}$ - but it is defined for any vector over $\mathbb{Z}_q$.

The basic idea here is to use a continuation from a smaller domain to a larger one.


RSA Timing Attack on "Extra" Montgomery Reduction

Montgomery multiplication
Theorem (Montgomery, 1985). For any odd integer $N$ and any integer $0 \le T < N2^k$, one has: $$T 2^{-k} \equiv \frac{T + UN}{2^k} \pmod N$$ where $U = T N' \bmod 2^k$ and $N' =  -N^{-1} \bmod 2^k$.  Further, one has: $$\begin{cases} T+UN \propto 2^k\\ 0\le \frac{T + UN}{2^k} < 2N\end{cases}$$
The last 2 properties show that $R:=T2^{-k} \bmod{N}$ can be computed in two steps as:

$R \gets \frac{T+UN}{2^k}$
If $R \ge N$ then $R \gets R - N\qquad$ (extra subtraction)

Montgomery arithmetic represents an integer $0\le x <N$ as $\tilde{x} = x2^k \bmod N$.  It defines the Montgomery multiplication of two representatives $\tilde{x}$ and $\tilde{y}$ as $$\tilde{x} \otimes \tilde{y} := (\tilde{x}\cdot\tilde{y})2^{-k} \bmod N\tag{*}$$  Observe that letting $z= x\cdot y \bmod N$, one has $\tilde{z} \equiv (x\cdot y)2^k \equiv (\tilde{x}\cdot \tilde{y})2^{-k} \equiv \tilde{x} \otimes \tilde{y}\pmod N$.
Timing attack
Suppose that each Montgomery multiplication, cf. Eq. ($^*$), is done using the above two-step process.  We see that depending on $\tilde{x}$ and $\tilde{y}$, there may be an extra subtraction to get the result $\tilde{z}$ in the range $[0, N)$.
To fix ideas, suppose that the computation of $S = m^d \bmod N$ is carried out with the square-and-multiply algorithm.  The attack can easily be adapted to other exponentiation algorithm. The algorithm takes as input a message $m$ and private exponent $d = (d_{\ell-1}, \dots, d_0)_2$.

$R_0 \gets \tilde{1}$; $R_1 \gets \tilde{m}$
for $i=\ell-1$ downto $0$ do
$\quad R_0 \gets R_0 \otimes R_0$
$\quad$if $d_i = 1$ then $R_0 \gets R_0 \otimes R_1$
endfor
return $\tilde{R_0}$

The goal of the attacker is to recover the value of $d$.  Observe that the square-and-multiply algorithm processes the bits of $d$ from the left to the right.

Let $d = (d_{\ell-1}, \dots, d_0)_2$
At step $j$, the attacker

 already knows bits $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$
 guesses that next bit is $d_j=1$
 chooses $T$ random messages $m_1, \dots, m_T$ and computes $$X_t = m_t^{(d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1},1)_2} \bmod N\quad\text{for $1\le t \le T$}$$
 prepares two sets $$\mathcal{S}_0 = \{m_t \mid \text{subtraction}\}\quad\text{and}\quad \mathcal{S}_0 = \{m_t \mid \text{no subtraction}\}$$
plays all messages in set $\mathcal{S}_0$ and obtains the average running time $\tau(\mathcal{S}_0)$ for an exponentiation; does the same for $\mathcal{S}_1$ and obtains $\tau(\mathcal{S}_1)$
if $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \not\approx 0$ then $d_j=1$ (the guess was correct); if  $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \approx 0$ then $d_j=0$ (the guess was incorrect)

Iterate the attack to find $d_{j-1},\dots$

In the above description, set $\mathcal{S}_0$ denotes the set of messages such that there is an extra subtraction at iteration $i=j$ in Step 4 of the square-and-multiply algorithm (i.e., Montgomery multiplication $R_0 \otimes R_1$) for the computation of $X_t$; set $\mathcal{S}_0$ denotes the set of messages such that there is no extra subtraction at iteration $i=j$ for the computation of $X_t$.
Note that the attacker can evaluate the exponentiation $X_t$ by herself as she knows $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$.  Further, since $d_j$ is assumed to be $1$, the last operation of this exponentiation $X_t$ will be a Montgomery multiplication $R_0 \otimes R_1$ (i.e., Step 4 is executed at iteration $i=j$).
Correctness
If $d_j=1$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ will be greater than the average time for an exponentiation for messages in set $\mathcal{S}_1$ because there is always an extra subtraction for $\mathcal{S}_0$.
If $d_j=0$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ or in set $\mathcal{S}_1$ will be (roughly) the same because the sorting between the two sets looks like random. Remember that the attacker made the guess $d_j = 1$.


Voting scheme where the votes become public when a threshold is reached

I am making the following assumptions regarding your requirements:

The number of participants is low enough, for it to be feasible for each participant to open a reliable, authenticated and confidential communication channel to each other participant.
The vote of each individual participant is only meant to be kept secret until the threshold of votes has been reached, at which point it becomes public how each participant voted.
System parameters $p, q, g$ are selected in advance, such that the discrete logarithm problem in a sub group of prime order $q$ of might be assumed to be hard.
The participants should not be allowed to change their votes once their votes have been cast, and collusion between participants must be prevented.
The risk of individual participants invalidating the election by opting out, is relatively low, and when it happens, it can be dealt with by starting over.

Given the above requirements, a simple approach would be to combine a binding and computationally hiding discrete logarithm based scheme with Shamir Secret Sharing.

Steps:

Each participant $P_i$ selects a value $x_i$ uniformly at random from $\mathbb Z_q$, calculates $h_i = g^{x_i} \bmod p$, and broadcasts $h_i$ to all other participants.
Each participant computes $h = (\Sigma_1^nh_i)^{(p-1)/q} \bmod p$. If $h$ equals zero, step 1 is repeated. (Extension: Each participants broadcasts $h$ and some protocol is in place to disqualify users who broadcast a value the majority of the other users find to be incorrect. For simplicity, this has been left out at this stage and the rest of the stages of the protocol.)
Each participant $P_i$ selects a degree $t$ polynomial $p_i(x)$ with coefficients $a_{i,1},..,a_{i,t}$ selected uniformly at random from $\mathbb Z_q$ and $a_{i,0}$ representing the vote of the participant.
In order to vote, each participant $P_i$ selects $n$ values $r_{i,j}$ uniformly at random from $\mathbb Z_q$, keeps them secret, broadcasts a commitment sequence $C_{i,j} = g^{p_i(j)}h^{r_{i,j}}$, sends $p_i(j)$ with confidentiality and authenticity to each participant $P_j$ who has already voted and gets $p_j(i)$ back from $P_j$.
Once at least $t+2$ votes have been cast, each participant broadcasts its $r_{i,j}$ values and all of the $p_j(i)$ values it has received from other participants.
Each participant verifies that each value $C_{j,k}$ it received when user $P_j$ voted, meets $C_{j,k} = g^{p_j(k)}h^{r_{j,k}} \bmod p$. (If not, some protocol has to be in place to disqualify users.)
Each participant solves the shared secret of each other participant and broadcasts the result.
Some protocol is in place to confirm that a majority of the participants have broadcasted the same result.

Q: Does this protocol really prevent collusion?

A: Strictly speaking, no. Nothing prevents the participants from conducting informal out-of-band exit polls during the voting in step 4. No protocol has any influence over what the participants do out-of-band, so this is something that has to be dealt with out-of-band as well.

Q: Is the Shamir Secret Sharing component really necessary? Since all participants who vote have to be online during the entire protocol, wouldn't a commitment scheme and a counter be sufficient?

A: If the possible votes are "Yea" (1) or "Nay" (0), using Shamir Secret Sharing allows a minor modification to the protocol, by which the total number of votes are counted before each individual vote is revealed. Each participant $P_j$ reveals the sum of the $p_i(j)$ values. Together with the corresponding sum of $r_{i,j}$ values, this sum can be verified using the commitments. Reconstructing a polynomial from those summed up shares, will equal the number of "Yea" votes.

Now, if some participant (e.g. the last one to reveal its sum) chooses to opt out, this user might be disqualified and the rest of the participants might wait for the next vote to be cast. No individual vote will have been revealed (through the protocol), but it is possible that the disqualified participant already knows the result (and is the only one who knows it).

Q: Isn't constructing the $h$ generator as a sum, rather than a product, susceptible to doctoring by the last participant to submit its $h_i$ value?

A: Not if we assume that $q^3 \lt p$ and every participant verifies that each $h_i$ belongs to the $q$ order subgroup. Also, constructing it as a sum allows for each participant to open their $x_i$ value, to prove that they know the discrete logarithm of $h_i$, without making it possible to calculate $log_g(h)$