Here's a nice paper I came across a while ago: Wooding, Mark (2008), "New proofs for old modes", Cryptology ePrint Archive, report 2008/121:

  "Abstract: We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter mode. Our results improve over those previously published in that (a) our bounds are better, (b) our proofs are shorter and easier, (c) the proofs correct errors we discovered in previous work, or some combination of these. We provide a new security notion for symmetric encryption which turns out to be rather useful when analysing block cipher modes. Finally, we pay attention to different methods for selecting initialization vectors for the block cipher modes, and prove security for a number of different selection policies. In particular, we introduce the concept of a `generalized counter', and prove that generalized counters suffice for security in (full-width) CFB and OFB modes and that generalized counters encrypted using the block cipher (with the same key) suffice for all three modes. "


Password entropy much lower than entropy of encryption keys. Why is this acceptable?

I know that humans would find it impossible to maintain a 128 bit password -- however, I wonder if there is some technical reason why a 52 bit password would not be as weak as a 52-bit encryption key for that matter.

First, I would argue that 128 bits is not impossible to remember. My current password manager master password is almost 100 bits (6 words from a large dictionary) and I could increase it to 128 bits if I wanted to by tacking a couple of extra words at the end.

However, yes, there are reasons passwords with much less entropy are often considered acceptable:

It is good practice to use a good password hash that slows down attacks to a similar degree as e.g. an extra 20 bits of entropy would.
Many uses of passwords do not allow an offline attack with as much computing power as the attacker has. E.g. a login password on a website can only be attacked online, usually with a strict rate limit. (Until the password hashes are stolen.)
Two-factor authentication is seeing some use. With it finding the password alone is insufficient.

When some of the above factors do not apply you need to make sure you have enough entropy. E.g. a "brainwallet" Bitcoin password does not benefit from 2. or 3. so it should have at least the 50+ bits so that a password hash makes attacking it too expensive to be worth the effort.


If I'm reading your question right, you've made two simple math mistakes:

The solution to $-1 \equiv -15a \pmod{26}$ isn't $a = 15$; it's $a \equiv 15^{-1} \pmod{26}$, or $a = 7$.
I'm not sure where you got $b = 3$, but it's not correct, either.  The right solution, using the correct value of $a = 7$, is $b = 19 - 2a = 19 - 14 = 5$.

(FWIW, using the incorrect value $a = 15$ should've given you either $b = 15$ or $b = 25$, depending on which of the two original congruences you plugged the wrong $a$ into.)

With the correct values of $a$ and $b$, your decryption formula works just fine: $a^{-1} = 7^{-1} \equiv 15 \pmod{26}$, so:

\begin{aligned}
15 \times (19 - 5) &\equiv \phantom{0}2 \pmod{26} \\
15 \times (20 - 5) &\equiv 17 \pmod{26}.
\end{aligned}

Both of your mistakes seem like simple lapses of concentration.  Maybe you just need to take a break from your homework and go get some sleep first.


None of them is secure. Both include dramatic privacy risks:

PEPP-PT build a a central database with all social interactions
D3-PT allows for linking of infection reports to individuals:

Simply record all Rolling Proxymity Identifiers you see and there timestamps with a simple continuously scanning BLE device (e.g. Raspberry Pi)
Process this list against the infection warnings.
You now only need to match this timestamps with other transactions on entrances, point of sale, CCTV or logon

D3-PT also allows nation states to contact trace suspects by

injecting fake alerts in seized mobiles
suppressing alert display during risk analysis (like silent SMS work),
but using risk analysis to identify individuals

A similar technique can be used with active beacons to find out who was at a certain place at a certain time
Someone can relay (receive with an own device, transmit via internet anywhere, send out to somewhere else with  an BLE extender) all broadcasts received near a covid test station to self quarantine anyone.


Hash functions with variable and fixed length inputs

Suppose you want to hash a pair of bit strings $(m, r)$ with a hash function $H_0$ defined on bit strings, where $m$ is variable-length and $r$ is fixed-length—maybe a unique salt, or a secret key, or an unpredictable randomization.  We will consider possible functions $H(m, r) := H_0(\operatorname{encode}(m, r))$ for some encoding function (although there are other possible ways to hash tuples using an iterated hash function).

First, what security properties are you hoping for when you say ‘hash’?  Here are some possibilities:

Independence.
If $r \ne r'$, then the functions $m \mapsto H(m, r)$ and $m \mapsto H(m, r')$ are (effectively) independent functions.

Here we are modeling $H_0$ as a uniform random choice of functions with quirks like the length extension attack below; we are interested not in how $H$ behaves on different messages with the same $r$, but rather how $H$ behaves with different $r$.

This is important for password hashing, because techniques like rainbow tables provide a batch advantage trying to find inputs $m_1, \dots, m_n$ given the outputs $h_1 = f(m_1), \dots, h_n = f(m_n)$ of the same function[1][2].  However, you should use a serious password hash like scrypt or argon2 if you're hashing passwords, and they are already defined in terms of separate password and salt parameters.
Collision resistance.
It is hard for the adversary to find $(m, r) \ne (m', r')$ such that $H(m, r) = H(m', r')$.  This is a standard property of functions like SHA-256 and BLAKE2b; if it holds for $H_0$ we might hope that it holds for $H$.

This is important for commitments: you can prove to someone that you have a message $m$ without revealing it by picking $r$ uniformly at random and revealing $h = H(m, r)$; then when you want to reveal what the message was, you can give them $(m, r)$ and they can verify $h = H(m, r)$.
(Enhanced) target collision resistance.
It is hard for the adversary to find a message $m$ such that, given uniform random $r$ after choosing $m$, they can find $m' \ne m$ and $r'$ with $H(m, r) = H(m', r')$.

With mere TCR[3] (first introduced to the literature as the less-pronounceable UOWHF[4]), the adversary is restricted to $r' = r$; with eTCR[5], the adversary is allowed to choose $r'$, so eTCR is a stronger requirement.

(e)TCR is important for randomized signature schemes like RSA-PSS and Ed25519.  The first secure signature scheme in history, Rabin's, used a randomized hash.  Even if $H_0$ turns out to have collisions like MD5, there are choices for $H$ that remain eTCR to the best of our knowledge.  Using a TCR construction would have thwarted MD5 certificate forgery, including a particular attack used by the governments of the United States and Israel to sabotage Iran's nuclear program—but RSA, Inc., and the IEEE adopted $H_0(r \mathbin\| H_0(m))$ instead of $H_0(r \mathbin\| m)$ in the standards[6][7] for PSS signatures.  (More history.)
Pseudorandomness.
It is hard for an anyone who doesn't know $r$ to distinguish the function $m \mapsto H(m, r)$ from a uniform random function of the same shape.

Pseudorandomness is useful for many things including deterministic key derivation and message authentication codes.

These properties aren't exhaustive, but they're likely to be relevant in a wide variety of applications.

What encoding might we use to define $H$ in terms of $H_0$, and what properties does the resulting $H$ provide?  Let's assume $H_0$ is an iterated hash function, like essentially all of them, and let's assume for simplicity that $m$ an integral number of blocks long.

Suffix-MAC: $H(m, r) := H_0(m \mathbin\| r)$, putting $r$ at the end.

provides independence
provides exactly as much collision resistance as $H_0$: a collision in $H$ is a collision in $H_0$ and vice versa
provides at most as much (e)TCR as $H_0$ provides collision resistance: finding a collision in $H_0$ is enough to break (e)TCR of $H$—so, no (e)TCR for MD5 or SHA-1!
provides at most as much pseudorandomness as $H_0$ provides collision resistance, for iterated Merkle–Damgård functions with no output filter like MD5 or SHA-256: finding a collision in $H_0$ is enough to distinguish $H$ from uniform random—so, no pseudorandomness at all for MD5 or SHA-1!

Prefix-MAC: $H(m, r) := H_0(r \mathbin\| m)$, putting $r$ at the beginning.

provides independence
provides exactly as much collision resistance as $H_0$: a collision in $H$ is a collision in $H_0$ and vice versa
provides at least as much (e)TCR as $H_0$ provides collision resistance: an (e)TCR break of $H$ implies a collision in $H_0$, but finding a collision in $H_0$ does not necessarily help to find a collision in $H$—e.g., nobody has broken eTCR for MD5 in this form
provides no pseudorandomness for for iterated Merkle–Damgård functions with no output filter like MD5, SHA-256, and SHA-512, for which length extension attacks apply: given $H(m)$ but not $m$, it is easy to find $H(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$, which a uniform random function exhibits with negligible probability—so, no pseudorandomness for MD5, SHA-1, SHA-256, SHA-512!

Exception: If $m$ is fixed-length, then prefix-MAC provides pseudorandomness under reasonable assumptions about $H_0$ even when $H_0$ is MD5, SHA-256, or SHA-512.
Note that SHA-3, BLAKE2, SHA-512/256, and essentially all new designs in the past decade do not have this weakness, so $H(r \mathbin\| m)$ is pseudorandom—but they usually also provide separate keyed hashes like KMAC128 or keyed BLAKE2, which are better to use because they are effectively independent even if you happen to hash the message $r \mathbin\| m$ with SHA-3 or unkeyed BLAKE2.

Envelope-MAC or sandwich-MAC: $H(m, r) := H_0(r \mathbin\| m \mathbin\| r)$, putting $r$ at the beginning and the end.

provides independence
provides exactly as much collision resistance as $H_0$
provides at least as much (e)TCR as $H_0$ provides collision resistance
provides pseudorandomness under reasonable assumptions about $H_0$

This is a predecessor to HMAC and actually it provides about the same security as HMAC with less complexity, as long as $m$ is padded so that the $r$ keys appear in their own blocks; it was left in the dustbin of history mainly because someone noticed that it does not provide security if the trailing $r$ straddles a block boundary[8] and thereby gave it a bad reputation, but it has since been proved that with appropriate padding it is a perfectly good choice[9] (paywall-free).
HMAC: $H(m, r) := H_0\bigl((r \oplus \mathrm{opad}) \mathbin\| H_0((r \oplus \mathrm{ipad}) \mathbin\| m)\bigr)$, using prefix-MAC first to compress the message and then as an output filter, with two keys derived by a simple key schedule.

provides independence
provides probably about the same collision resistance as $H_0$
provides at least as much (e)TCR as $H_0$ provides collision resistance
provides pseudorandomness under mostly reasonable assumptions about $H_0$


How they work

Public and private keys work as follows. Every party who wants to communicate with others generates a private key which they keep secret. From that private key, they derive a public key, which they publish for anyone to see.

For example, if we have three agents, Alice, Bob, and Charlie, they will all have a secret key S_A, S_B, and S_C and a public key each, P_A, P_B, and P_C.

If Alice wishes to encrypt a message to Bob, she uses Bob's public key for encrypting the message. To decrypt the message encrypted with his public key, Bob must use his respective secret key.

How they are made

You don't need to understand how public and private keys are made to understand how to use public-key cryptography. It is only necessary to understand the following basic concept: While there is a one-to-one correspondence between a public and a secret key, it is computationally easy to go from the private key to the public key, while it is computationally hard to go from the public key to the private key.

Such problems form the basis of asymmetric cryptography and are abundant in computer science. For example, the factoring problem has this asymmetry. If I give you two prime numbers p and q (the private key), you can readily evaluate their product n = pq (the public key). However, if I give you the public key and I tell you it's the product of two large primes, it is hard for you to find these two primes even though there's only one unique solution. The factoring problem is in fact used in the RSA cryptosystem. Other problems that have this asymmetric property are problems on lattices and the discrete logarithm problem in finite groups.

How they are exchanged

Exchanging public keys is easy. Public keys can simply be published, as they are not secret. For example, they can be published on a newspaper, spoken over the phone, sent on an email, or uploaded to public key servers.

How does asymmetric encryption work?

This is a more complicated question that you don't need to understand to move on and use public-key cryptography. The math is somewhat convoluted. It is also specific to various cryptosystems. The easiest to understand is the RSA cryptosystem. To understand it, you need to study some basic algorithms and facts such as the Fundamental theorem of arithmetic, the Extended Euclidean Algorithm, the Miller-Rabin primality test, Fermat's Little Theorem and its extension Euler's theorem. Following this knowledge, Wikipedia's explanation of RSA can be understood without much effort.


How to calculate the entropy for a fixed length random passwords which has restrictions on the type of characters used

It looks like the formula you're using is $\log_2(\textrm{number of possible passwords})$.
You don't explicitly mention a length, so I'll assume 10.
So with those restrictions, let's calculate the number of possible passwords.
Without any restrictions, the total number of possible passwords is $94^{10}$.
Let's count the number of invalid passwords.
$(94-26)^{10}$ don't contain an uppercase letter. $(94-26)^{10}$ don't contain a lowercase letter. $(94-32)^{10}$ don't contain a special character. $(94-10)^{10}$ don't contain a digit.
There's overlap in those. For example, $(94-52)^{10}$ contain neither uppercase nor lowercase letters.
Number of invalid passwords = $(94-26)^{10} + (94-26)^{10} + (94-32)^{10} + (94-10)^{10} - \left((94-52)^{10} + (94-58)^{10} + (94-36)^{10} +(94-58)^{10} + (94-36)^{10} + (94-42)^{10}\right) + \left(26^{10} + 26^{10} + 32^{10} + 10^{10}\right)$
This yields $64.81$ bits.

Sanity check:
Ignoring order, The restrictions give $26 \cdot 26 \cdot 10 \cdot 32 \cdot 94^{6}$ possible number of passwords. That's one uppercase, one lowercase, one digit, one special character, and the remaining 6 can be anything. Taking the $\log_2$ of this yields $57.05$ bits.
This is a lower bound. The $65.5$ you mention in the question provides an upper bound. The answer lies inside the bounds as expected.


You could view it as a form of One-Time-Pad encryption. In this view one of the two "messages" is the key and the other is the ciphertext (it does not matter which you think of as which as their roles are symmetric).

It may, however, be more natural to think of as a simple secret sharing scheme. Roughly speaking a secret sharing scheme is a scheme where a secret is divided into a number of shares. Usually you then need more than some specified number of shares to reconstruct the secret, and any lower number of shares will give no information on the secret.

For your scheme $m$ is then the secret, $m_1$ and $m_2$ are the shares and you need both shares to reconstruct the secret.

The scheme you describe is a well known and much used one, sometimes referred to as "XOR" sharing. This because you can define the shares as picking random bits $m_1, m_2$ under the restriction that $m = m_1 \oplus m_2$.


This has been (re-)defined in RFC 3279: "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile". For DH section 2.3.3: "Diffie-Hellman Key Exchange Keys" applies:

Here is the ASN.1 module (which was copied from X9.42, so this is at least a copy of a copy):

  DomainParameters ::= SEQUENCE {
        p       INTEGER, -- odd prime, p=jq +1
        g       INTEGER, -- generator, g
        q       INTEGER, -- factor of p-1
        j       INTEGER OPTIONAL, -- subgroup factor
        validationParms  ValidationParms OPTIONAL }

  ValidationParms ::= SEQUENCE {
        seed             BIT STRING,
        pgenCounter      INTEGER }

So it at least $p$, $g$ and $q$, but the co-factor $q$ is usually set to 1. This set has been defined for OID 1.2.840.10046.2.1 ("dhpublicnumber").

However, when trying this for myself using openssl command line, I only got two parameters, $p$ and $g$. Turns out openssl is using PKCS#3 instead:

  DHParameter ::= SEQUENCE {
        prime    INTEGER, -- p
        base     INTEGER, -- g
        privateValueLength INTEGER OPTIONAL }

which has been defined for OID 1.2.840.113549.1.3.1 ("dhKeyAgreement").

So yeah, $p$ and $g$ are certainly in there, which set of parameters are in there depends on the OID that defines the key type of the public key and the choices of the organization implementing it. That's a lot of options for something that is barely used.


What communications security protocols exist that aren't based on PKC?

The answer is to your problem is called Transport Layer Security with Pre-Shared Keys (TLS-PSK) and is widely available in implementations.

TLS-PSK offers PKC aided and non-aided key-exchanges, with the former being recognizable by the DHE, ECDHE, RSA parts in their names. This means you want to look for the TLS_PSK_WITH_* cipher suites.

In particular I'd recommend you using TLS_PSK_WITH_AES_128_GCM_SHA256 (or the 256/384 version thereof). If your platform doesn't offer SHA-2 and / or AES-GCM your best choice would be TLS_PSK_WITH_AES_128_CBC_SHA.

Note that TLS-PSK will take care of all the security issues, with the protocol (TLS v1.0, v1.1, v1.2, v1.3, newer versions are preferrable, v1.3: draft version 10 linked) taking care of the protocol level issues using the cipher suites for the message layer issues.


Number of combinations required to brute force

You're actually describing a use case for cryptographic hash function (not encryption). A cryptographic hash is a one-way-function that is collision-resistant. Meaning that it is hard to guess a pre-image (input to the function) that will generate a given result (called a hash).
Cryptanalysis of schemes like this assume that there is some structure or predictable property of the plaintext, such as letter frequency or word choice.
Let's assume that all of your users pick 4 words as their password (xkcd pass). And they choose it out of reasonable words in /usr/share/dict (about 50k words).
This is a strong password selection method, so if this scheme doesn't hold up under this plaintext pattern, it is most likely breakable under other password schemes.
Iterate through each word in the file, reverse it, and XOR it with the start of the password. We then take the result and do a look up in the sorted dictionary file (sorted during pre-computation). If this is a match, we've discovered two of the words and can recurse on the inner portion of the hash to find the last two words. This attack method assumes that all of the words are the same length, but I believe it can be easily adapted for various word lengths.
This attack will only take $\Omega(n*logn)$ steps of precomutation (for sorting the words file). And then $2*n*logn$ time for 100% guaranteed reversal of each hash. For a cryptographic hash (or one-way-function), you want a hash scheme to be secure in an exponential ratio to the number of bits, such as $\Omega(2^n)$, so this scheme is insecure.


It would make sense to encrypt as many bytes as possible at the same time. For example, a word like apple can be written as this sequence of byte values in hexadecimal 61 70 70 6c 65. You can treat this as a 40-bit number 0x6170706c65, which is equal to 418498243685. When this number is retrieved after decrypting the ciphertext, just convert it back into hexadecimal to get the original byte values.

Obviously you would need an RSA modulus of at least 40 bits to encrypt a word of this length. In practice, it would have to be a lot longer than that. An important part of RSA encryption is the use of randomized padding. Without it, the word apple would always be encrypted to the same value, so an attacker could easily encrypt every word in the dictionary and compare the results with your ciphertext to find out what word you had encrypted.

Standard padding schemes like OAEP recommend the use of at least 64 random bits to ensure that the likelihood of the same word being encrypted the same way is negligibly small. You also need to ensure that your modulus can't easily be factored, which means it should be a number of at least 1024 bits.


Having trouble understanding reduction functions in rainbow tables

In this case, how can a reduction function like taking the last 6 characters of a hash as a reduction function serve in a rainbow table trying to find a password such as Password123?

It can't. Assuming the reduction function takes the last six bytes of output it can only be used to generate passwords up to 6 (ASCII) characters long.

To crack any password up to 6 characters long you need to precompute a number of hashes on the order of $256^{6}$. That takes more space/time than is actually needed. If you don't target passwords that use non-ASCII or non-printble ASCII characters then you can reduce $256^6$ to about $95^6$. ($95$ being the number of "printable" characters.)

So then you substitute your reduction function that simply reinterprets binary data, substituting 6 bytes of hash output for a six character long string, with a more complex function. You can convert the bytes of output to a base 95 number, then create an ASCII string where each value 0 through 95 corresponds to one of the printable ASCII characters.

You don't want to use the first reduction function because it creates unlikely passwords. No ASCII string with any character in the range [0, 31] or [127, 255] is likely to be a real world password, so your rainbow table will be inefficient if you use this reduction function.

The base-95 example I gave is one reduction function that improves efficiency because it avoids characters from these two ranges. For six bytes of hash output you could actually generate 7 character long passwords. (Because $\log_{95} (256^6) \approx 7.30$)

More efficient reduction functions could be used but they would need to be more complex. Maybe you want to rule out candidate passwords that have 4 or more of the same letter in a row unless it's in the form "aaaa.....a" or "aaaa...123". Then you have to make assumptions about what is considered a "likely" password in the real world and then you need to find a way to implement it efficiently.

There are tradeoffs to such choices. If you omit a string from the set of possible outputs that a reduction function can produce then your rainbow table can not crack those passwords if they're used in the real world. If the reduction function can't produce a string then the rainbow table can't crack that password.

You can crack a larger set of potential passwords by increasing the amount of bits your reduction function uses. In the naive implementation you can crack passwords up to six characters long if you use six bytes. Or seven characters if you use seven bytes. And so on.

But when you grow that password set you also need to do more precomputation (and us more time and/or memory during querying). In practice you get diminishing returns by using more and more bytes.

If you don't do precomputation work proportional to the entire then your table will only cover a fraction of all possible passwords. If your password set is $X$ elements large and you do $X \over 2$ work then less than half of those candidate passwords will actually be covered by a rainbow table.

A larger candidate password set size means you need to do more hashing, even for rainbow tables. Rainbow tables are not effective for targeting long low-entropy passwords. Instead dictionary based cracking and rule-based-brute-force cracking is used.

Rainbow tables are not the go-to algorithm for password cracking anymore. It is a precomputation-based cracking method. Any precomputation method for sound password hashes using cryptographic hash algorithms can easily be made ineffective by using a unique (per-password) random salt.

Today, people attempt to crack correctly hashed passwords by using brute force methods that run in parallel. GPUs differ from CPU hardware in that they do identical operations in parallel. GPUs have many more (simpler) cores than CPUs have, so the are better at doing certain tasks in parallel.

Rainbow tables aren't so important anymore where proper password hashing (with salts) is used. And they never really worked very well for long passwords.


How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?

Notation is basically a free choice of the author, as they describe functionally the same. And there is no fixed definition for this. However, common practice in mathematical publications is:

Multiplicative notation for arbitrary groups
Additive notation for commutative groups

This can be found here: math-SE,  wolfram

Wikipedia also states, that additive notation is primarily used for modules and rings. However, that is quite obvious because for those you need both types of notations.

Interestingly, in cryptography we rarely see any non-abelian groups except matrix multiplication, yet multiplicative notation is quite common. The emphasis here might be on the difficulty of the discrete logarithm problem: If a group has the property, that calculating DLOG is difficult, we tend to use multiplicative notation. Additionally, we note generic groups in multiplicative notation mostly.

Additive notation is used mostly just for elliptic curves, or of it is actually a group operation derived from the addition of integers. In that case it might be used to emphasize: In this group the DLOG problem is easy.


Attacks on AES-128 (ECB) based on some knowledge of plaintext

If the protocol doesn't provide authentication, an attacker can probably mount replay attacks or make deterministic changes to messages.

If the nonces in different blocks are not compared in any way, they can just take the ID block of a previous message and use it with a new one, to forge it being from that device. If nonces are required e.g. to be equal in all the blocks of a message, the attacker can still reorder them freely, which reorders the message in the same way. If there are any blocks without nonce, those can be freely moved within and between messages.

  One of the plaintext blocks it encrypts has a 4-octet nonce followed by 12-octets that are always the same (part of the device's unique ID).

A 32-bit nonce means you need to see on average $2^{16}$ such blocks from the same ID + key to see a collision. Even seeing just a few hundred gives an attacker a larger chance to see one than is usually considered secure. Such a collision shows the attacker the two messages came from the same device/ID.

  I'm looking for basically anything that could compromise the security of the protocol, so anything that significantly narrows down the keyspace, or even the possible values for those 12 constant octets.

You cannot find the key even with known plain/ciphertext pairs (unless it's been chosen in a non-random way that allows an attack). If the attacker ever sees two blocks with equal ciphertext, they will know the plaintexts are equal and may be able to derive information about the ID, depending on which block matched which.


Using RSA public key as private key and vice-versa

I am writing an application that involves checking to see if data has been created by me.

That's known as verifying data that was signed. It is good practice.

  I do this by encrypting the data with the private key on my server, and then decrypting it using the public key on the client.

That's where it gets wrong. The server must sign with the private key, and then the client must verify the signature with the public key. In RSA there are commonalities between sign and decrypt (both include the private-key operation $x\mapsto y=x^d\bmod N$), and between verify and encrypt (both include the public-key operation $y\mapsto x=y^e\bmod N$), but there also are important differences. For this reason, well-designed APIs, and knowledgeable advisers, won't let you encrypt with the private key. Don't even try. Ever. Forget about it.

Since the API includes PSS, which is a signature padding, it most likely includes primitives to sign with RSASSA-PSS. We are not a code review site, thus I won't try to find where. But my reading of hazmat is that primitives in that area are not meant for direct use, I would look elsewhere.

Edit: I do not immediately see an issue with the code as it now stands, except for naming tag and variable encrypted, which I guess are for a signature. But then I do not know this API, and we are not a code review site.


Probability of generating same master secret key in Identity-based Encryption

Yes, it is possible, but extremely improbable.

Take for example the BasicIdent IBE scheme, by Boneh and Franklin. Let us assume that the curve, pairing and groups are fixed. During the Setup step, one has to select a random generator $P \in \mathbb G_1$ and a random master key $s \in \mathbb Z_q^*$. We can assume that these parameters are sampled uniformly.

The probability of selecting the same parameters in a different domain mostly depends on selecting the same $P$ and $s$. The order of both $\mathbb G_1$ and $Z_q^*$ is $q$, so the probability of generating the same system parameters is $\frac{1}{q} \cdot \frac{1}{q} = \frac{1}{q^2}$, which is negligible.


Password hashing alogirthm simple enough to implement myself?

The PBKDF2 construction is simple to implement, and can be implemented with any underlying hash function.

Unlike modern password hash functions, the end result will be computationally intensive, but won't have any resistance against parallelization. Not requiring much memory means that ASICs can efficiently brute-force passwords hashed that way.


Why do the subexponential algoriths for the DLP not work for the ECDLP?

"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime.
The intuitive reason why the DLP is harder to solve over (well-chosen) elliptic curves is that they are our best construction of a generic-like group, id est a group with seemingly no more structure than the group law. It is known that over a generic group of order $q$, the best algorithm to solve DLP takes $O(\sqrt{q})$ steps.
However, fields do obviously have way more structure than generic groups, and this structure can be exploited. More precisely, there is a family of algorithms, called Index Calculus, tailored to exploit this structure. Note that for some elliptic curves, DLP can be solved via index calculus, hence ECDLP requires "well-chosen" elliptic curves.
Index calculus algorithms work by creating a large base of the relation between the discrete logarithm of small prime values. This system of equations is then solved to get the discrete logarithm of each element of the factor base. Let $(g,h)$ be the DL instance. Next, the algorithm tries to write $g^sh$ as a product of powers of the factor base, for some $s$. Once it finds such an $s$, finding the discrete log of $h$ in base $g$ is easy.
The core notion to answer your question is the need for a base of small prime values: although well defined for a field, "prime" cannot be defined for generic groups, or for elliptic curves. Hence, the index calculus cannot be used on well-chosen elliptic curves. Still, some elliptic curves are affected by the index calculus when there is some map which moves the DLP problem from the curve to some field.


Partial Known Message Pre-Image Attack on SHA-1

If you know the last 448 bits, we can assume that this part actually the padding part with length at the end, then you will have 64-bit unknown data for the input to pre-image attack. Since you know the output hash value you can set up a system of equations. In this case, the hash function can be considered as

$$\operatorname{F}:\{0,1\}^{64}\times\{0,1\}^{448} \to \{0,1\}^{160}$$

Now, for every output bit, set up an equation by algebraic evaluation of SHA-1. You will have 160 equations and 64 unknowns.

This type of system is called over-defined when there are more equations than unknowns. However, keep in mind that the system may be inconsistent that means there is a collision there an that has an expected negligible probability.

According to Bard, Courtois, and Jefferson paper;

  if the system of equations is sparse or over-defined, then the SAT-solver technique works faster than brute-force exhaustive search. If the system is both sparse and over-defined, then the systems can be solved quite effectively.

The only problem that we can't see, immediately, the degree of the equations. If they are low degree then the SAT solvers, as Mini-SAT, can be faster than brute-force, according to the result of the paper.


Does anyone sell a proprietary symmetric encryption alogirthm?

Yes. One prominent commercial example is Cypto AG, a company in switzerland. Its clients include some nation states. Of course most major nation states have their own proprietary diplomatic and military symmetric key algorithms.

See the Crypto AG website here.

Historically, they have been involved in some controversies. See one example report here.

Googling will yield much more on Crypto AG and its history, usual caveats apply. The main objection is lack of open peer review.

Edit: References to Crypto AG's proprietary algorithms are given below. I am not claiming these are secure algorithms, FWIW.

The link here has a company document from 2007:

"For encryption, the proprietary HCA-480 crypto algorithm is used in combination with Customer Managed Profiling (CMP), offering a variety of over 10506. The Communication Key (CK) is 128 bits long and is used to generate a key stream with a period of more than 1028 years."

A newer link is here:

"All systems are based on the sophisticated Crypto Security Architecture, which comprises elements such as a tamper-proof hardware module, customer-controlled and proprietary algorithm [..] emanation-proof hardware (COMPREM) and a flexible security and network management."


Using RSA encryption with OpenSSL library: secure?

New systems should not use RSA unless interoperability requires it. See for example this twitter thread for current zeitgeist: https://twitter.com/veorq/status/1148258833896263680

With RSA, the recommendation is to not even have a mode where data is encrypted using RSA directly, even if it fits. Always use hybrid encryption to not have two code paths. The symmetric encryption part should use a modern AEAD, and unless the performance difference between AESGCM (up to 5GB/s) and ChaPoly (up to 2GB/s) is important, use the ChaPoly since a random implementation of ChaPoly is more likely to be secure than a random implementation of AESGCM.

Instead of RSA-OAEP, I would use Curve25519 ECDH in ephemeral-static mode. Meaning you create a Curve25519 keypair, store the private safely offline and copy the public to the system that will encrypt.

Every time it needs to encrypt a file it generates a new Curve25519 keypair, writes the public into the beginning of the encrypted file, does ECDH between the private and the destination's public to get a shared secret, forgets the newly generated Curve25519 keypair, uses KDF over the DH shared secret, and uses the result of the KDF to generate key and nonces for the AEAD. If the cleartext is long, use chunks.

To decrypt, use the private key stored offline to do the ECDH with the ephemeral public, KDF, AEAD.

Oh wait, I'm describing libsodium. Use libsodium. It is the embodiment of 20 years of lessons learned in cryptography and misuse resistant crypto API design, it is production quality, it is portable, it is fast, etc.

If large quantum computers ever happen, both Curve25519 and RSA would be broken. Details about the future quantum computer are not available to judge whether using larger RSA would give you more safety margin (unless you use post quantum RSA, which is a joke).


Multiple private keys for single public key

Public-key algorithms such as RSA or ECDSA have exactly one private key for each public key and vice versa.

Attribute-based Encryption

Attribute-based encryption works (a little bit) like that. You have only one public key which is used to create all ciphertexts and you select the users that should be able to decrypt the data based on a policy of attributes. The policy can be a boolean formula and the users have secret attribute keys that should satisfy the policy if they must be able to decrypt the ciphertext.

If you use only one attribute for all users and a trivial policy containing that attribute, you've got that system that you wanted, but now the problem becomes that the user attribute secret keys have to be generated by a central server and you will need multi-party computation to get rid of the key escrow.

Conventional

This is almost certainly too complicated for your case. You should use a symmetric algorithm like AES and a public key encryption algorithm like RSA in conjunction. You can simulate your intended system by encrypting the data with AES using a randomly generated key, then encrypt the AES key with all the RSA public keys of the intended recipients. Concatenate everything into one package and send it on its way.

Thoughts

Let's say multiple recipients have (a different) private key and all of them can decrypt data encrypted with the same public key. You should ask yourself, how can the different private keys be generated to arrive at the same public key, but where all the recipients wouldn't know the private key of each other.


Prime order elliptic curve groups: Generators and the reason choice

Yes, by Lagrange's Theorem in the group theory, the order of any element must divide the order of the group. Therefore, except for the identity element, which has order 1, all other points can be a generator.
If you define a protocol, you need a common agreement and the generator is a part of this. If you don't include it in the specifications you need to agree for every user. Instead of this, one point is assigned as the basepoint.
Normally the base points are selected in the manner of nothing-up-my-sleeve-numbers to show that there are no backdoors designed. The choice reason is given as

The generators of G1 and G2 are computed by finding the lexicographically smallest valid x-coordinate, and its lexicographically smallest y-coordinate and scaling it by the cofactor such that the result is not the point at infinity.

BLS12-381 is used for digital signatures and zero-knowledge proofs in Zcash, Ethereum 2.0, Skale, Algorand, Dfinity, Chia, and more.


Randomizing before Shamir secret sharing?

As I understand, the security of key-sharing depends on the cleartext
  actually being random.

Actually not, the premise of the Shamir Secret Sharing (SSS) scheme is that it is information-theoretically secure.

That means if you require $N$ shares for reconstruction and an attacker has $<N$ shares, the following equation holds:
$$\Pr[M=m\mid C=c]=\Pr[M=m]$$

Which basically says that given the ciphertext you know as much about the plaintext as you know without having the ciphertext.

Or, put differently, as tylo said in the comments:

  He can guess, but he can't check if his guess was right.

As for why this holds (as you may ask yourself now): Notice that SSS basically encodes your secret as the point $(0,s)$ and that the shares are points $(x,f(x)), x\neq 0$ of a (nearly-random) polynomial of degree $N-1$ over some field (usually $\mathbb F_p^*$). Now imagine as an example you're given 2 points of a degree-2 polynomial (which would be N-1 shares). For every possible $s$, you can now find a third point such that $(0,s)$ is on the polynomial. Put otherwise: There's no additional constraining condition that would help you narrow specific plaintexts down as more likely.


What does it mean to have "signature verification with RSA-4096" if the key is only 3072 bits long?

Two possible interpretations:

"The RSA key sizes supported are 1024, 2048, and 3072 bits" could mean that RSA key generation and/or private-key operations (signature generation, perhaps decryption) is supported only for 1024, 2048, and 3072-bit key (really, public modulus) size; while "up to RSA-4096 signature verification" would apply only to signature verification, or more generally public-key operations (also including encryption).
The restriction to 1024, 2048, and 3072 bits could apply only in the so-called "FIPS mode", because FIPS 186-4 section 5.1 and by extension FIPS 140-2 conformance only allows these particular key sizes when using RSA.


Could a larger block size increase the security of the block cipher?

TL;DR: a larger block size won't help to make the block cipher itself more secure, but it can be used to make the schemes using the block cipher more secure.

The block size basically determines the number of possible permutations: the possible ways to combine all the possible plaintext blocks with the possible ciphertext blocks. The number of permutations grows much faster per bit of the block size than the number of possible keys from the key size. In that sense it is unlikely that a larger block size will do much for the security of the cipher.

Modes of operation however do rely on the block size for other purposes. For instance, the counter size of AES-CTR is defined to be the same size as the input block size. That counter usually consists of a random nonce and a counter part, for instance 64 bits for the nonce and 64 bits for the counter. However 64 bits is not that much for a nonce; as the birthday problem applies you can only encrypt about $2^{32}$ ciphertext before the counter could repeat. Now this isn't a huge problem, but it would be avoided with a block size of 256 bits (or, indeed a tweak, or both).

Specific constructions could also require a larger block size. For instance a hash function generally relies on large state. To go from one large state to another a block cipher could be used. Obviously it would need to have a large state and a large block size itself. There are other ways to do this with a cipher with a smaller block size but it won't be as efficient.


Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis

I think you're being too dismissive and thinking of this as a "side project".

The challenge is representing the action of the cryptographic mappings such as the key schedule and the round functions which result in a pseudorandom permutation that can only sample a vanishingly small subset (a fraction $$\frac{2^k}{(2^n)!}$$ for keylength $k$ block length $n$, which are usually the same, but not necessarily) of all permutations in $S_{2^n}$.

The key is random, but the subkeys are not, they are directly derived from the key, so you have $k$ bit maximum key entropy used typically for $kr$ total subkeys bits.

More importantly, you need a worst-case approach while to my understanding the mixing time convergence to uniform is more of an average case criterion.

Are you aware of work by Lai-Massey-Murphy, Luby Rackoff. You can start by tracking the references to those.

And poly time mixing may tell you hundreds of rounds are enough on average but you'll want to use sublinear number of rounds.

This answer focused on block ciphers alone.


Is AES-Keywrap (NIST SP 800-38F) quantum-safe?

The Kuwakado-Morii attack (the attack of Kaplan et al. is a nice adaptation of this) relies crucially on Simon's algorithm, which essentially says that on the group $(\mathbb{Z}/2)^n$, the hidden shift problem is easy.  That is, from quantum access to $H(\cdot)$ and $H(\cdot\oplus s)$, it is possible to recover $s$ efficiently.

On the other hand, the Key-wrap algorithm of NIST SP 800-38F does not use group structure.  Well, at least not much: while some constants are XORed during the execution of the algorithm, no adversarially-controllable data are ever XORed during the computation: the whole process is mostly built using shuffling and blockcipher evaluation.

Of course, we cannot really know whether it would be secure until we prove the security, but some constructions not relying on group structures (not even XOR) are known to be quantum-secure: for example, Zhandry proved that the GGM construction is a secure PRF, and, it happens that GGM uses only function composition, not group structure.

At the least, I think this suggests that Kuwakado-Morii is not really applicable here.


Why is 2048-bit RSA always paired with 320-bit ECC?

As far as I know, there is no mathematical trick to put hardware doing a full modexp engine (with modulus register meaningfully sized for RSA) to good use for ECC; an hypothetical such engine is bound to get very much under-utilized with the typically much smaller modulus used for ECC.

However, in Smart Cards, hardware support for RSA does not use such engine; rather it is used a dedicated a co-processor with some moderately wide wordsize $w$ bits, matching multiplier, and a small RAM with wide databus. Arguments are split into $w$-bit chunks just as is done on regular CPUs. RSA and ECC are built on top of that using microcode for that coprocessor, and software in the main CPU. Up to some limit for $w$, processing time decreases as $2^{-2w}$. Public details are scant, but consistently $w$ is many times below the width of an RSA secret prime (typically 512-bit at the very least), and at least often below the width of the public modulus for the group on which the ECC curve is built (typically 160-bit at the very least).

So my guess on what limits the RSA and ECC key size supported by Smart Card RSA and ECC accelerators are:

The size of the RAM accessible by the coprocessor, which at least sometime is dedicated and uses a sizable portion of the silicon. That might sometime answer the question. The RAM size accessible by the coprocessor is closely tied to the upper bound for RSA; it also defines a different bound for ECC; and that later bound is much lower because point multiplication requires a much larger number of intermediate values the size of the base group.
What's achievable at decent speed given word width $w$ of the coprocessor. Going to the next number of chunks might be impractical even if there is enough RAM, as time is proportional to roughly the cube of the number of chunks (for ECC: to the square of the number of chunks times hash width, but since the number of chunks is lower, going to the next number of chunks creates an even wider gap).
Market demand: standard key sizes are few, which combines with 2 to make the upper size commercially supported rather arbitrary.

Note: I'm not confirming the numbers in 2048-bit RSA always paired with 320-bit ECC. In fact, most modern Smart Card ICs I see around support higher limits, substantially so for RSA.


Problem statement

You have a list of messages $(m_1, m_2, \dots, m_n)$, possibly with corresponding tags/descriptions $(t_1, t_2, \dots, t_n)$, that you want to store. You want to protect confidentiality of the messages (but not the tags/descriptions) against an adversary that compromises your storage. You have a single secret passphrase $pw$ at your disposal.

The adversary may know/be able to guess part or all of some or all of the messages.

Your solution

What you propose (based on AES-OFB, $c = \mathrm{AES{-}OFB{-}}\mathcal{E}(k, m)$, $m = \mathrm{AES{-}OFB{-}}\mathcal{D}(k,c)$, the encryption algorithm generates the IV and includes it with the ciphertext; your software may have a different interface):

Generate a salt $s_0$.
For each entry, generate a salt $s_i$.
For each entry, compute $k_i = \mathrm{PBKDF2}(pw, s_0 || s_1, \mathit{iterations})$.
Compute $c_i = \mathrm{AES{-}OFB{-}}\mathcal{E}(k_i, m_i)$.
Store the two lists $(c_1,c_2, \dots, c_n)$ and $(t_1, t_2, \dots, t_n)$.

Q&A

Q: Do you need the per-entry salts?
A: No. The salt is there to keep the per-passphrase search cost high for attackers that have compromised the stores of many users. The salt $s_0$ is sufficient.

Q: Is it a problem that the adversary can guess/know part of the message?
A: No. AES-OFB provides confidentiality against chosen plaintext attacks.

More than you asked for

You shouldn't be doing this kind of design on your own, nor should you rely on advice given on a random web site.

Don't think that the adversary won't be able to recognize correct passwords.
Don't assume that the user will be able to recognize an incorrect decryption.
Don't use OFB mode. It is sometimes inefficient and does not provide integrity.

The following natural proposal is better than yours (based on AES-GCM, a symmetric encryption scheme that encrypts messages and protects the integrity of associated data as well: $c = \mathrm{AES{-}GCM{-}}\mathcal{E}(k, ad, m)$, $m = \mathrm{AES{-}GCM{-}}\mathcal{D}(k, ad, c)$. (Note that I am assuming that the encryption algorithm generates a fresh IV/nonce for each encryption and attaches it to the ciphertext. Your software may have a different interface.))

Choose a salt $s$.
Use PBKDF2 (or something similar) to derive a key $k$ from $s$ and $pw$, using a suitable number of iterations.
Encrypt each secret as $c_i = \mathrm{AES{-}GCM{-}}\mathcal{E}(k, i || t_i, m_i)$.
Store the two lists $(c_1, c_2, \dots, c_n)$ and $(t_1, t_2, \dots, t_n)$.

PS. Don't use a scheme you got for free on the internet.


Is exponentiation of a fixed generator modulo a prime collision-resistant?

Let $m$ be arbitrary. Then $m'=m+p-1$ yields a collision with $h(m)=h(m')$ as $m\equiv m'\pmod{p-1}$ and thus by $p-1$ being the relevant group's order $g^m\equiv g^{m'}\pmod p$.

Or formulated differently (using $g^{p-1}\bmod p=1$): $$h(m')=g^{m+p-1}=g^m\underbrace{g^{p-1}}_{1}\equiv g^m=h(m)\pmod p$$


The existence of partial homomorphic additive encryption with bit-wise XOR operation

Assuming the finite field is of odd characteristic (that is, $GF(p^k)$ for some prime $p > 2$, then such an encryption operation would be FHE; and would be much bigger news than just only solving the Millionaire problem.

With such an encryption method, given $E(a)$, $E(b)$ and a constant $c$, we can compute $E(c)$,$E(a \oplus b)$, $E(a + b)$ and $E(c \times a) = E(\underbrace{a + a + ... + a}_{\text{c times}})$ (where the addition and multiplication are within $GF(p^k)$,   If we can't compute $E(c)$ directly, we can just place $E(c)$ within the public key (assuming that the range of possible $c$'s is limited).

So, assuming $a, b$ are restricted to $\{0, 1\}$, we can compute the NAND operation $E(\overline{a \wedge b}) = E( 1 \oplus (k \times ((a + b) \oplus a \oplus b)))\ $ for the constant $k = 2^{-1} \pmod p$.  It is straightfoward to see that this function gives $E(1)$ if either of $a, b$ is 0, and $E(0)$ otherwise.

With this encrypted NAND function, we can construct any circuit.


If I send a signed email, how does the end user get the public key?

You can send the public key certificate as an attachment with the email or you can send the public key certificate in a separate email.

The main point is the end-user should receive the public key for verification.

A certificate can be a file e.g. *.cer . The end user needs to have a program to verify the document.

UPDATE:
Chances of an MIM attack or other attacks always exist. But having more than one form independent communication can help the situation along. E.g. send the key in soft form (usb/CD) with a courier service. Or talk to the person you send your public key to and ask them to open the key in a text editor and tally first and the last line of the key. Or use public key database/storage providers like PGP does.


Performance of RSA encryption when the public exponent is 3 and 65537

This can be due to various reasons, most likely more than one:

First use of that key initializes some data that takes longer to compute than your actual public key operation (for example, sliding window initialization can take as long as public key operation). Since you only perform one operation per key, this makes this probable.
Your key is so short that it is relative to time other stuff takes (padding, calling the library,various checks on input data, splitting and synchronizing threads [in case of private key operations with Chinese Reminder Theorem]).
Your measurement of time is not precise enough.
Your library uses protection against time side-channel. This is very likely if you are using OpenSSL or other well-studied library, since those are usually secure against most side-channels, but this is usually only done for private key operations.
Other things, like processor not having data in it's cache or branch mis-predictions and background work can also be a factor, especially since you didn't mention that you ran public key computation in loop. For example, if your computer decides to do a thread-switch across your measurement, it can make your result seem lot longer.

Generally, you should execute your computation so long that it actually takes more than few seconds to compute, to avoid small factors that invalidate your results. Also, you should be sure that your library doesn't protect against side-channels in your specific scenario. Only then those measurements can be deemed accurate enough to look deeper.

But this usually isn't padding that is case for time being same. Padding is usually at least 10x faster than public key computation (even when public key operation is hand-optimized SSE2 assembly).

My best guess is that your computation is simply not precise, with both not using accurate timing, and executing computation doesn't take long enough (especially executing public-key operation just once per key isn't enough).

UPDATE

You said that you use python's time.time(). On my machine it has 1ms resolution. Now, since you have to start measurement, then stop it after you ended your encryption (since then you generate new key), this adds to inaccuracy of your measurement. Also, you compared your results to Java and C which both are compiled, and therefore I assume quite a lot faster. It could be that simply everything involved in calling proper functions takes far longer than encryption itself. Adding inaccuracy of time.time() this makes your result of 5sec for both quite probable.
To maximize chance of finding difference, I'd recommend generating one key, then encrypting result multiple times, and timing it all.
Since PyCrypto uses built-in pow, I've checked if results differ, and indeed they do in my very simple test. I've got 832ms for 3 and 5200ms for 65537 (for a fairly small prime and 100000 iterations of pow).


Using a LibSodium CryptoBox KeyPair with `crypto_sign`

It's possible to go the other way around (thanks Scott Arciszewski)

<?php

$sign_pair = sodium_crypto_sign_keypair();
$sign_secret = sodium_crypto_sign_secretkey($sign_pair);
$sign_public = sodium_crypto_sign_publickey($sign_pair);

$key_secret = sodium_crypto_sign_ed25519_sk_to_curve25519($sign_secret);
$key_public = sodium_crypto_sign_ed25519_pk_to_curve25519($sign_public);

$key_public = sodium_crypto_box_publickey_from_secretkey($key_secret);

?>


How can I force slow decryption in the browser?

As I indicated in the comments, I believe a non-cryptographic solution may be the best for this task, where instead of attempting to measure "10 minutes" by the average amount of time it takes to do some computational task, you simply measure it by the wall-clock time. Note that this solution still uses some cryptography, but not as a proxy to measure 10 minutes.
Concretely, when a user wants the document, you can generate a key (say an AES private key) $k$, create a payload = $k || D$ where $D$ is the current date/time formatted in some standard way, let $h= H(k || D)$ be a hash of the payload, and then store $[h, k, D]$ in some table, and send $h$ to your user, along with the document (encrypted under the key $k$).
The user can then query you later with some hash $h'$. Upon recieving such a query, check if $h$ is in your stored table as part of some entry $[h, k, D]$. If so, and if at least 10 minutes have passed since the date/time $D$, return the key $k$ to the user, who can now decrypt. You can also evict the table entry $[h, k, D]$ at this point.
The pros/cons of this versus a "intentionally slow decryption" solution are:

There is less wasted computational effort on the part of the user

The limit of 10 minutes is enforced regardless of the user's particular architecture (and their desire to "cheat")

The operations on the server side of things are likely more efficient than the other RSA-based solution (for example, you have to use ~128 bits of randomness per user, instead of >2k for RSA to be secure).

The cons are:

The user has to query your server a second time
You must store some intermediate state for each user (the $[h, k, D]$). This should be rather small (a few hundred bits) per user, but is greater than zero.

I think it is worth mentioning that I expect it would be difficult to get a uniform "10 minute decryption time" in the browser using time lock puzzles, even among honest users. I have not thought through this in detail, but I imagine that differences in hardware architectures (especially with respect to the presence of certain SIMD instructions, i.e. Intel SSE / AVX type instructions) may be able to get a constant factor speedup on your users architectures in the underlying BigInt multiplication for RSA, which would then result in users having architecture-dependent decryption times.
If you implement things correctly (and make sure that auto-vectorization does not occur), you may avoid this issue. But even differences in clock speed (say 2GHz vs 3.5GHz, or whatever numbers are reasonable for a few-year-old phone vs a enthusiast's desktop) would likely make a big enough difference that it would be difficult to enforce a 10min decryption time for all users (you could likely ensure that decryption for all users takes at least 10 minutes, but for some users it may take 20 minutes, or whatever).


The key is the password.

For the first iteration, the salt concatenated with the desired output length in bytes is the input.
U1 = PRF(Password, Salt || INT_32_BE(i))

For subsequent iterations, the HMAC result is the salt.
U2 = PRF(Password, U1)
...
Uc = PRF(Password, Uc-1)


How multiplicative property of RSA can be exploited

Using this property, you can't fully break RSA (meaning you can't get the private key).

However there are a few attacks.

If you're using RSA for public-key encryption, there's an adaptive chosen ciphertext attack. Suppose you want to decrypt $c$ and A is decrypting everything but $c$ for you. Now you can chose your $c_1=x^e*c$ with $x\in Z_n^*$. Now you you send $c_1$ to A, he decrypts this. Now you'll have $m_1=c_1^d=c^d*(x^e)^d=m*x$ $(mod$ $n)$, now you simply compute $m=m_1*x^{-1}$ $(mod$ $n)$ and decrypted an arbitrary ciphertext
If you're using RSA for digital signature with message recovery you can basically mount the same attack as above, by basically using blind signatures so you can get arbitrary data signed. (If not using proper methods to protect)


Necessary to authenticate nonce if authentication-key is derived from nonce?

Yes. Assuming KDF and AuthEnc are secure and you are using them with correct prameter lengths, the first one is secure.

Usually, you would use 2nd and authenticate everything because if s.o. tempers with the nonce, he might be able to alter the plaintext without changing the MAC.rrect parameter lengths, yes your first scheme is secure.

In any proper AE(AD) scheme, the nonce is used in both the ciphertext and the MAC generation so tampering with it will inevitably lead to a MAC verification failure.

The only thing I would change is dropping the nonce calculation. There is not really a point in deriving the nonce from your master key, if you already know unique_message_nonce is actually unique (and that is all that most popular AEAD schemes like GCM and CCM need).

I would even prefer version one over the second one. It is a lot simpler for the developer and AE(AD) schemes were built for just what you want. The fewer steps you have to do yourself, the fewer errors you can make.


Does the Biclique attack on AES pose a credible risk to its security?

Simply put no.

As per the abstract, those attacks take at most 4 bits off the key space, this still results minimally in 124 bits of security. Put another way, to use these attacks you would need to expend effort roughly proportional to brute forcing an AES key where you already knew four bits of the key and this would take approximately $2^{124}$ operations.

For reference, the standard rule of thumb on security is it must provide about 80 bits currently. Of course, this is to be secure now and not 100 years from now and and something that provides 80 bites of security now could have those eroded later. However 124 is still more than enough of a safety margin.


Encrypt user email but be able to find user by email

I ended up with the following solution:
For each email store two values: encrypted email and signature for the email.
For encryption I used AES in CBC mode with random IV.
For signing I used HMAC SHA256.
The keys used for encryption and for signing are different.

Later on I found the following link: docs.oracle.com. So looks like this is pretty standard approach.


Why is the re-encryption algorithm in Universal Re-encryption for Mixnets more complicated than apparently necessary?

Actually no, it is not related to CCA security.

The re-encryptor mix server needs all of the four components for performing a correct re-encryption since it does not know the public key of the receiver $g^x$. Mix server only knows $\alpha_0, \beta_0, \alpha_1, \beta_1$ and two re-encryption factors it generates $k''_0, k''_1$

The encrypted message mix server receives:

$$[(my^{k_0}, g^{k_0}); (y^{k_1}, g^{k_1} )] = [(\alpha_0, \beta_0); (\alpha_1, \beta_1)]$$

The re-encrypted message it sends:

$$[(my^{k'_0}, g^{k'_0}); (y^{k'_1}, g^{k'_1} )]= [(\alpha_0\alpha_1^{k''_0}, \beta_0\beta_1^{k''_0}); (\alpha_1^{k''_1}, \beta_1^{k''_1})]$$

The scheme is designed in a way that not only it does not require the public key, the ciphertexts and the re-encryption procedure do not yield any information about the public key. As a result, it could be used in applications that require "receiver-anonymity" in situations that we have multiple receivers.

Page 2 of the paper:

  The novelty in our proposal is that re-encryption neither requires
  nor yields knowledge of the public key under which a ciphertext was computed.


Hint: what happens if the prover, instead of sending $g^r$ for a random $r$ that he knows in the first round, sends instead $g^{-x}\cdot g^r$ for a random $r$ that he knows?


Proof of work scheme with one and only one correct answer

One obvious approach would be look at a discrete log problem.  That is, you pick an appropriate group of order $n$ (where $n$ is prime) and a generator $G$; for a challenge, you pick a random element $H$, and you ask for the value $0 \le k < n$ such that $H = kG$.

This meets your requirements (1) the value produced is effectively random, requirement (2) one can search for the answer in $O(\sqrt n)$ time, (3) if $G$ is a generator, then there is exactly one such value, and (4) the answer can be verified in $O(\log n)$ time. In addition, the amount of work is tunable (by selecting groups of various sizes).

For this to work, we need to select a group where we can't find discrete logs faster than $O(\sqrt n)$ time; I believe an appropriately sized random Elliptic Curve meets this requirement.

However, the chief difficulty with this suggestion is finding an Elliptic Curve group of the appropriate size; that's nontrivial, and all the precomputed Elliptic Curve groups I know are scaled to make the discrete log problem "infeasible", not "difficult".

Another group that would appear to be suitable is a small subgroup of a larger multiplicative group.  That is, we pick a large prime $p$ and a small prime $q$ where $q | p-1$.  We will then work in the multiplicative subgroup of size $q$ of the group $\mathbb{Z}^*_p$.  To create a random element of this subgroup, we select a random number $1 < x < p$, and compute $H = x^{(p-1)/q}$.  The order of the subgroup is, of course, $q$, and so if the work target is about $2^{32}$ operations, we may select a 1024 bit $p$ and a 64 bit $q$.  The chief advantage of this proposal over the Elliptic Curve idea is that it is much easier to devise a $p$ and $q$ of the appropriate sizes, rather than trying to define an Elliptic Curve.


AFAICT, this framework injects entropy directly into the underlying cryptographic primitive instead of treating the entropy collection/estimation and randomness extraction as two separate phases. Is my understanding correct?

Yes, that's my understanding as well.

What quantitative benefits does this framework have over the more traditional seed-based design?

The benefit is that if the entropy source is under partial control of an attacker it will still be possible to create a secure random number generator, assuming that enough entropy is left of course. If you assume that the entropy pool is not under control and delivers enough entropy to a traditional PRNG using the seed(s) then the benefits seem non-existent. Here's where I struggle a bit, because "partial control" seems to be tricky to accomplish.
In the traditional approach you could argue that the PRNG requires another PRNG-like construction (such as a KDF or, in the case of Intel, a PRF/MAC) to create the short, universally random bit string to be used as the seed.


Specification of the Megamos crypto algorithm

As cybergibbons notes in his answer, the court decision itself is quite interesting reading.  In particular, while the details of the "Megamos algorithm" itself are obviously not given in the court decision, the manner in which it is used is described in a surprisingly clear manner in paragraphs 4 and 5:

"In detail the way this works is as follows: both the car computer and the transponder know a secret number. The number is unique to that car. It is called the "secret key". Both the car computer and the transponder also know a secret algorithm. That is a complex mathematical formula. Given two numbers it will produce a third number. The algorithm is the same for all cars which use the Megamos Crypto chip. Carrying out that calculation is what the Megamos Crypto chip does.
"When the process starts the car generates a random number. It is sent to the transponder. Now both computers perform the complex mathematical operation using two numbers they both should know, the random number and the secret key. They each produce a third number. The number is split into two parts called F and G. Both computers now know F and G. The car sends its F to the transponder. The transponder can check that the car has correctly calculated F. That proves to the transponder that the car knows both the secret key and the Megamos Crypto algorithm. The transponder can now be satisfied that the car is genuinely the car it is supposed to be. If the transponder is happy, the transponder sends G to the car. The car checks that G is correct. If it is correct then the car is happy that the transponder also knows the secret key and the Megamos Crypto algorithm. Thus the car can be satisfied that the transponder is genuine. So both devices have confirmed the identity of the other without actually revealing the secret key or the secret algorithm. The car can safely start. The verification of identity in this process depends on the shared secret knowledge. For the process to be secure, both pieces of information need to remain secret - the key and the algorithm."

Translated (back) into standard crypto terminology, it appears that the "Megamos algorithm" is an (evidently failed) attempt to implement a pseudorandom function family (PRF).
Specifically, the authentication protocol described in the paragraphs above can be rephrased as follows:

Both the car computer $\rm C$ and the transponder $\rm T$ hold a shared secret key $K$ and a pseudorandom function family (implemented using the Megamos algorithm) $\sf PRF$, of which ${\sf PRF}_K$ is a specific instance parametrized by the key $K$.  The PRF outputs a bitstring that is split into two parts, $F$ and $G$.  To perform an authentication exchange:

$\rm C$ chooses a random number $r$ and computes $(F,G) = {\sf PRF}_K(r)$.
${\rm C \to T:}\ r, F$
$\rm T$ computes $(F',G') = {\sf PRF}_K(r)$ and aborts unless $F = F'$.
${\rm T \to C:}\ G'$
$\rm C$ verifies that $G = G'$.

Now $\rm C$ and $\rm T$ have verified that they can each compute ${\sf PRF}_K$, and therefore hold the same key $K$.

An interesting feature of this protocol is that, since $r$ is chosen solely by $\rm C$, an attacker who manages to eavesdrop on a legitimate exchange could easily impersonate $\rm C$ by replaying the earlier $r$ and $F$, and could even verify $\rm T$'s response by comparing it with the earlier $G$.  Under the expected usage scenario, this might not be considered a major security risk, since the important part is presumably authenticating $\rm T$ to $\rm C$; on the other hand, since the protocol evidently does try to also authenticate $\rm C$ to $\rm T$, it might simply be that the summary above is incomplete, and that the actual protocol uses some additional mechanism to prevent such replay attacks.
That said, other than the flaw described above, the protocol seems solid provided that $\sf PRF$ is indeed a secure pseudorandom function family.  In particular the assertion in the court decision that "[f]or the process to be secure, both pieces of information need to remain secret - the key and the algorithm" appears patently false: if the algorithm were a secure PRF, such as, say, AES-CMAC-PRF-128, the protocol described above would be secure as long as just the key $K$ was kept secure.
Indeed, the same holds regardless of the details of the protocol: by definition, any instance of a secure pseudorandom function family is indistinguishable from a truly random function, as long as one does not know the key used to choose the instance.  Thus, by definition, the choice of the algorithm, or the manner in which it is used, does not matter as long as it's a secure PRF: they all look identical to anyone who doesn't know the key.  Indeed, there are many published and freely usable PRF algorithms that have withstood extensive public scrutiny and cryptanalysis, and are in common use worldwide.  By failing to publish their own algorithm (or to use one of the already published algorithms), the makers of the Megamos Crypto chip have not only violated Kerckhoffs' principle, but also deprived themselves of this scrutiny by the global crypto research community.
All that said, I can easily enough understand why they may have chosen to do so: the Megamos Crypto chip is designed to be embedded into a car key, with all the attendant limitations on memory capacity and power consumption.  Implementing standard crypto primitives like AES on such small, low power devices is often a challenge, and of the few crypto algorithms specifically designed for such devices, most are new and still poorly analyzed, not to mention that even the published designs often end up making questionable tradeoffs in speed vs. security.  The designers of Megamos Crypto may have been hoping that, by designing their own algorithm and keeping it secret, any security weaknesses it may have might not be so easily exploited.
Alas, Kerckhoffs' principle has a habit of reaffirming itself: if there's profit to be made in discovering the algorithm, someone will do so and profit from it.  Indeed, based on the court decision, in this case this appears to have happened long ago, by 2009 (when the algorithm was included in the Tango Programmer tool, sold for €1000 by a Bulgarian company and described in the court decision as being of "clearly murky origin") if not earlier.

By the way, the court decision even quotes some interesting parts of the redacted paper, including the following, which sheds some light on the nature of the weaknesses discovered in the Megamos algorithm:

"Unfortunately, our first attack is hard to mitigate. It seems unfeasible to prevent an adversary from gathering two authentication traces. Furthermore, this attack exploits weaknesses in the course of the cipher's design - e.g. the size of the internal state. It would require a complete re-design of the cipher to fix these weaknesses. To that purpose, lightweight ciphers, like grain, and so on, have been proposed in the literature and could be considered as suitable replacements for the Megamos Crypto. On the positive side, our first attack is more computationally intensive than the attacks in section 6 and 7, which makes it important to take the aforementioned mitigating measures in order to prevent the more inexpensive attacks."

Earlier in the text, the defendants also note in their case (paragraph 19(xiv)) that:

"The attack based on the Megamos Crypto algorithm still requires the criminals to have a car, plus a key, plus two days to use a computer program which tries out a lot of possibilities."

From the phrasing, and from the suggestion of Grain as an alternative, it appears that the "Megamos algorithm" may in fact be some kind of a stream cipher.  This does make sense, insofar as, with the input somehow combined with the key, a stream cipher may be regarded as PRF with arbitrary-length output.  Stream ciphers, despite their limitations as crypto building blocks, also still remain very popular as crypto primitives for low-end systems.
The attack itself appears to be some kind of a related-key attack based on comparing the output of the cipher for two different random nonces (which are made known during the authentication process) and presumably involving some kind of "informed brute force" enumeration of the internal cipher state in order to recover the secret (fixed) part of the cipher key.  Or at least, that's what it looks like based on the court decision.


Text in random image encoder: is it flawed?

This is flawed:

Cracking: The format leaks information on how often specific characters occur.
For instance, if input message contains 6 o letters, there is likely much more 111 values than the most other values present. Such a small biases are sufficient for cryptoanalysis to break the message in many cases.

Also, random.randint does not return random number suitable for cryptographic purposes, it means the scheme can be possibly broken. (See https://docs.python.org/2/library/random.html for guidance, which tells the function shall not be used for cryptographic purposes). In current versions of Python, the generator is Mersenne Twister, which is easy to reverse (break). (See http://b10l.com/reversing-the-mersenne-twister-rng-temper-function/). Long story short, an attacker can easily use the produced image to find the original seed of the random number generator and thus, be able to generate the key.

The system is not very space efficient: there is large overhead, the produced message is much larger than the input. (The technique primarily sounds more like steganography instead of cryptography.) Also, the key is longer than the message, and variable length.


How does the IV or initial counter increase internally for each block in AES CTR mode?

The entire block consists of a $n$ bit nonce and a $128-n$ bit counter. Typically $n=64$. The nonce needs to be large enough so that every message under the key can have a unique one, and the counter needs to be large enough that every message block can have a unique counter value.

Typically, the counter is initialized to 0 and then incremented by 1 for each block. However, this isn't mandatory, I don't think there's any reason for that choice beyond the fact that it's the simplest, clearest way to do it. Any initialization value and incrementing function is valid so long as the choice doesn't cause repeats of the counter for the desired message length. (Even the FIPS validation process allows submissions that implement CTR mode to choose both the initial value and the incrementing function their implementation uses.)


Crypto libary with Commutative Encryption

Why can't you use RSA? Look at their description of a function on pp. 41-42, and you'll see that it is a perfectly valid choice.

So you have two users, $A$ and $B$, who want to play. One user, say $A$, selects $p \cdot q = n$, as per $RSA$, and sends that information to $B$. Both $A$ and $B$ independently choose large primes (or large numbers they confirm are coprime to $\phi(n)$) $e_A$ and $e_B$, and then compute $d_ae_a \equiv 1 \pmod n$ and $d_be_b \equiv 1 \pmod n$. Then, $E_A = m^{e_A} \pmod n$, and so on.

Any crypto library with $RSA$ support should allow for calling the encrypt and decrypt functions with your choice of exponent and modulus. The one downside is needing to generate a reasonably large new public exponent for each hand, but that isn't too bad on a modern system.


XTEA is a block cipher. It requires a block cipher mode of operation to work. Together with a block cipher mode of operation you can generate something that is secure. For this you require at least an IV, as you may otherwise encrypt identical passwords (for different users) to identical values. Or, if you encrypt each character separately, the same character value to the same ciphertext.

A block cipher itself is a PRP, a pseudo random permutation. Given a key, it will always transform one plaintext to the ciphertext associated with it. If you use XTEA in e.g. Block TEA this will not be different; you will always get the same ciphertext.

You can do the following things:

define a character set for your password and possible input values;
encode the password using the said character set
pad the password to a certain maximum length, say 64 bytes to allow for pass phrases (either store the length or use an invalid character such as 00 hex)
generate a 8 byte IV (for a 64 bit block cipher such as XTEA; IV requirements may depend on mode of operation and block size)
encrypt the encoded & padded password using the IV and key
store IV | ciphertext

This should be secure, as long as the mode of operation you choose is secure. You may want to use authenticated encryption (e.g. GCM) for this, but that's not really a requirement.

Usually it is better not to store passwords at all, but this seems a requirement in your case. You may want to check if there are secure password faults available from the runtime environment. If there is no pressing argument for using XTEA, you should be using AES.


Constructing set membership proof for private set

Yes. $\:$ The verifier(s) need(s) to know a statistically binding commitment to $\Psi \hspace{-0.02 in}$.


extract password hashed in scrypt using hash and salt

The whole point of a PBKDF like scrypt is that you can't. So that if somebody hacks the server and retrieves the hash and the salt they cannot reconstruct your password which you might have used on other sites.


Zero knowledge proof of equality of discrete log and hash preimage

This paper (here also in case of a academic barrier) solves exactly the problem you have; just instantiate the garbling scheme with the hash function.

To prove the relation of the hash, they use a garbling scheme with the garbler being the verifier and the evaluator being the prover. Since the garbler has no inputs to provide into the garbled circuit, the verifier can 'open' the complete circuit to the prover after the prover has commited to the output key, which makes the performance comparable to garbing schemes secure against semi-honest adversaries (which is a lot faster than security against malicious adversaries) This paper (here also in case of a academic barrier) describes that in detail. The paper cited above now only combines that idea with 'common' commitment schemes.


How to encode bivariate polynomial in Predicate Encryption and Inner Product?

In general, to encode a polynomial $p(x) = a_n x^n + a_{n-1} x^{n-1} + ... a_1 x + a_0$, $$\mathbb{p} = (a_n, a_{n-1}, ... a_1, a_0)$$ and $$\mathbb{w} = (x^n, x^{n-1}, ... x, 1)$$

So for your univariate case, $\mathbb{w} = (x^2, x, 1)$. You can see that $\left<\mathbb{p}, \mathbb{w} \right> = p(x)$, and you substitute the attribute as you need. So I think your univariate case is correct.

For the bivariate case, it's the same, but with mixed powers. You'll have terms like $x_1^i x_2^j$, where $i+j \leq n$. So in the general case where $n=2$ with two variables / attributes, you have:

$$ p(x_1, x_2) = a_{20}x_1^2 + a_{11}x_1 x_2 + a_{02} x_2^2 + a_{10}x_1 + a_{01}x_2 + a_{00}$$

In your case, you have:

$$ p(x_1, x_2) = x_1 x_2 - x_1 b - x_2 a + ab$$

So $a_{20} = a_{02} = 0$, $a_{11} = 1$, $a_{10} = -b$, $a_{01} = -a$, and $a_{00} = ab$. Finally,

$$\mathbb{p} = (0,1,0,-b,-a,ab)$$

and

$$\mathbb{w} = (x_1^2, x_1 x_2, x_2^2, x_1, x_2, 1)$$

Again, you can see that $\left<\mathbb{p}, \mathbb{w} \right> = p(x_1, x_2)$.


ECC Complexity order of point addition, scalar point multiplication and selecting random point

It depends on the multiplication algorithm used. Let $n$ be the bit size of the finite field used, and let $O(n^k)$ be the complexity of the multiplication algorithm used (e.g. $k=2$ for schoolbook multiplication, or $k=1.585$ for Karatsuba multiplication). Then:

Point addition: $O(n^k)$ (a constant number of multiplications)
Scalar multiplication: $O(n^{k+1})$
Selecting random point: depends on the method, but usually the same as scalar multiplication.

As pointed out by poncho, the point addition (and the scalar multiplication) can require a multiplication inverse, whose complexity again depends on the algorithm and may be larger than the complexity of multiplication. For example, binary euclidean takes $O(n^2)$, Fermat's little theorem takes $O(n^{k+1})$.


If $G$ is set to $1$, then the adversary can easily decrypt the ciphertext because in this case $h = pf^{-1} \mod q,  p$ is coprime with $q$, then inverting  $p \mod q$ is possible and  after that he calculates $f \mod q$ from $h$, then he calculates $f^{-1} \mod p$ from $f$


Discrete logarithm problem particularly hard for Schnorr groups?

I do not know an exact citable source.

However the rationale is roughly the following:

The Decisional Diffie-Hellman Problem (DDHP) is not hard in $\mathbb{Z}_p^*$ since the Legendre symbol leaks the parity of the discrete log (DLOG) [1 section 5.1.2, 2]. You can use this fact to build an efficient algorithm to distinguish between Diffie-Hellman and non Diffie Hellman tuples [3 section 6.6].
Another reason is the existence of the Pohlig - Hellman Algorithm [1].

Note that the semantic security of the ElGamal cryptosystem rests on the DDHP problem, which is believed to be easier than the DLOG problem.

References:

[1]Cryptography: Theory and Practice by Douglas Stinson

[2] Finding $x$'s parity in the discrete log problem

[3] https://crypto.di.uoa.gr/class/Kryptographia/Semeioseis_files/Cryptograph_Primitives_and_Protocols.pdf


How to attack a "many-time pad" based on what happens when an ASCII space is XORed with a letter?

"Hint: XOR the ciphertexts together, and consider what happens when a space is XORed with a character in [a-zA-Z]."

Let's assume that the plaintexts consist only of spaces and ASCII letters.  Given the hint, that seems like a reasonable assumption to start with, even if it might turn out to be only mostly correct.

Now, take one of the ciphertexts and XOR it with each of the others.  Of course, the XOR operation cancels out the keystream, so you end up with the plaintext corresponding to the chosen ciphertext XORed with each of the other plaintexts.

Now look at each character position in turn.  By assumption, the character at that position in the chosen plaintext might be either a letter or a space.

If it's a space, then the characters at that position in the pairwise XORed plaintexts will be either letters (if the character at that position in the other plaintext is a letter) or nulls (if both of the characters are spaces).
If it's a letter, then the characters at that position in the pairwise XORed plaintexts will be random control characters (if the character at that position in the other plaintext is a letter with the same case), numbers or punctuation (if the other character is a letter with different case) or that particular letter with the case flipped (if the other character is a space).

Those two cases should be pretty easy to tell apart.  Furthermore, in the first case, you can easily get the actual characters at that position in all the plaintexts just by flipping the case of all the letters you obtained by XORing the ciphertexts together.

In this manner, you can decode all the characters at the positions where the plaintext corresponding to the chosen ciphertext has spaces.  Once you've done that, choose another ciphertext and repeat the process.  Hopefully, by the time you've done this with all the ciphertexts in turn, you will have solved most of the character positions and can easily fill in the rest.

Ps. To see why this works, it helps to know that the 7-bit ASCII character set can be divided into four 32-character blocks, like this:

Bit 4:     0000000000000000 1111111111111111 |
Bits 0-3:  0123456789ABCDEF 0123456789ABCDEF | Block:
---------+-----------------------------------+---------------------------
Bits  00 | ................ ................ | Control characters
5-6:  01 |  !"#$%&'()*+,-./ 0123456789:;<=>? | Numbers and punctuation
      10 | @ABCDEFGHIJKLMNO PQRSTUVWXYZ[\]^_ | Uppercase letters (mostly)
      11 | `abcdefghijklmno pqrstuvwxyz{|}~. | Lowercase letters (mostly)

In particular, a consequence of this structure is that, if you XOR two ASCII characters in the same row (e.g. two uppercase letters or two lowercase letters), the result will be a control character.  Similarly, XORing an uppercase and a lowercase letter will produce a character in the second row, i.e. a number or a punctuation character.  Also, as pointed out in the hint, the position of the space character at the beginning of the second row means that XORing it with any other character just flips bit the fifth bit of the character code, moving the character one row up or down.


From Schneier's description of DES in Chapter 12 of Applied Cryptography (12.3):

  DES with any number of rounds fewer than 16 could be broken with a known-plaintext attack more efficiently than by a brute-force attack.

This explains the "Why not less than 16".

As for the "why not more than 16", that is a tradeoff for speed of execution (more rounds = less speed).


When I need something on that tune I might use Jörg's useful and ugly page of mathematical data.

In particular, all-trinomial-primpoly gives primitive GF(2) trinomials (LFSR with 2 taps, the minimum number) to degree 400. 100,63,0 tells you that $x^{100}+x^{63}+1$ is primitive, meaning the same as 100|100,63 at LFSR Feedback Taps to 168 bits.

Also of interest is eq-primpoly-w5, giving one primitive pentanomial (LFSR with 4 taps) per degree up to 660. The entry 660 498 329 164 0 tells that $x^{660}+x^{498}+x^{329}+x^{164}+1$ is primitive (equivalent to 660|660,498,329,164 in a Feedback Taps table). Reference is given to: Janusz Rajski et Jerzy Tyszer, Primitive Polynomials Over GF(2) of Degree up to 660 with Uniformly Distributed Coefficients.

Further, highbit-normalprimpoly gives one primitive polynomial per degree up to 400, selected has having the lowest non-constant term as high as possible. That one is handy for software implementations, for the representation of the polynomials can be compressed into a small bitmask.


How can I create a stream cipher from a block cipher?

There are 3 modes of operation which make a stream cipher out of a block cipher:

Cipher Feedback Mode,
Output Feedback Mode, and
Counter Mode.

Taking example of the Counter Mode, this is how encryption and decryption works

$$C_i = P_i \oplus BlockEnc_k(count)\\
P_i = C_i \oplus BlockEnc_k(count)$$
$count$ is increased by 1 with every
 byte of the stream.


XOR is used here to flip about half the bits and create a large Hamming distance between the two versions of the key. It is not used to make the operation reversible. Making the operation reversible would not make sense in the first place: the hash that is applied afterwards is a one-way function and therefore not reversible.

The HMAC construction is used to make it impossible that collisions in the hash result in loss of security and to make sure that length extension attacks are not possible.

Bonus answers for the questions in the comment:

  Is authentication confirmed by the receivers knowledge of the pre-shared key?

Yes, message authentication is confirmed because the MAC can only be calculated if the sender has the same key as the receiver. Beware of replay attacks and communication reversal attacks though; these are not prevented by a MAC alone. In other words, you should uniquely be able to identify your messages and include that identification in the MAC for authentication.

  If we used AES with HMAC, would I need to compute this HMAC for every block of cipher text?

Yes, if you have ciphertext you need to authenticate all of it as well as the IV/nonce. If you're not sure which parts of the ciphertext to authenticate then you're better off using authenticated encryption (GCM or EAX for instance).


What is the adversary advantage for soundness of a sigma protocol?

No, the advantage of an adversary against soundness in a $\Sigma$-protocol is not 0. In fact, a $\Sigma$-protocol satisfies honest-verifier zero-knowledge, meaning that one can always "cheat" by running the zero-knowledge simulator against an honest verifier, provided that we manage to guess the challenge in advance. This means that any $\Sigma$-protocol will have soundness error at least $1/|S|$, where $S$ is the set of all possible challenges. Most $\Sigma$-protocols from the literature actually achieve this bound exactly.


How to argue to a paranoid that RSA is safe?

The security of every single cryptographic algorithm(*) of any kind is ultimately based on: "many people looked at it for a long time and did not find a way to break it". Security proofs boasted by some algorithms are quite useful but they don't actually prove security, they move it (a security proof is a reduction to another problem which has to be assumed to be strong).

So one could "measure" the strength of an algorithm by the accumulated scrutiny it has sustained successfully. In that sense, RSA is about the best in class: it relies on mathematical principles which can be argued to have been studied for more than 2500 years by the smartest mathematicians in the World. Elliptic curves cannot compete with that.

This argument is, of course, debatable. At best. Yet one has to take into consideration that paranoia, by definition, is a distortion of the perception of reality and the balance of risks. So the paranoid can be convinced by arguments which depend on that distortion.

(*) Except the very few algorithms with unconditional security, like Shamir's Secret Sharing, but they are limited in scope. That which is done with RSA (asymmetric encryption, digital signatures) can be easily proven to be infeasible with unconditional security; e.g. signatures can always be theoretically forged through exhaustive search on signature values, since the verification algorithm is, by definition, public.

Convincing people is actually a more psychological than cryptographic endeavour. Context matters. If the context is economical, then it suffices to say: "Maybe RSA can be broken, but your competitors use RSA. Not doing the same incurs the risk of letting them run ahead of you." Indeed, the paranoid is averse to risk, and not doing the exact same mistakes as the competition is the biggest risk that can be taken by a business.


Turning a cipher into a hashing function

Not only we can turn block ciphers into hash functions, but we do.

The usual hash functions (MD5, SHA-1, SHA-256...) use the Merkle-Damgård construction which relies on a block cipher E. A running state r is initialized to a conventional value. Then the input data is split into a number of chunks, each chunk being used as key for the block cipher: r is encrypted with E, using the current chunk as key; the result is added (or XORed) with r, and this yields the new state r for the next chunk. Last obtained state is the hash output.

If you want to apply the Merkle-Damgård construction on a standard block cipher such as AES, you will run into the following problems:

The size of the internal state is the size of the hash output, and it is also the block size of the cipher. AES is a 128-bit block cipher, leading to a 128-bit output, which is a bit too small with regards to today's technology (it would imply resistance to collisions only up to 264 evaluations, which is expensive but doable).
The MD construction exercises unusual features of the block cipher. In particular, the input data is used as key, and collision attacks (a major concern for hash functions) correspond to related-key attacks on the underlying cipher. Related-key attacks are not a problem for block ciphers when they are used for what they were designed to, i.e. encryption. AES is known to have slight weaknesses with regards to related keys but this is not a problem for encryption. It will become a problem if AES is used as building block in a MD-based hash function. (Resistance to related-key attacks was not a design criterion of the AES competition.)

Therefore, MD-based hash function use custom block ciphers which are designed to be especially robust against related-key attacks (or, at least, so we hope for). In the case of SHA-1, the inner block cipher was blessed with a name of its own, SHACAL.

Another example is Whirlpool, based on the block cipher "W", an AES derivative with a larger block size (512 bits) and a revamped key schedule to make it much stronger against related keys (and, unfortunately, it makes it much slower too). This addresses the problems explained above. (Whirlpool does not use the Merkle-Damgård construction, but Miyaguchi-Preneel, a distinct construction which has its own quirks.)

Yet another example is Skein, one of the SHA-3 candidates. It builds over an internal block cipher called Threefish; again, a block cipher with large blocks (512 bits in the "standard" Skein, extensible to 1024 bits).

A few SHA-3 candidates reused not the AES, but parts of the AES; in particular, ECHO and SHAvite-3. The idea was to be able to optimize the hash function with hardware meant to speed up AES, especially the AES-NI opcodes of recent x86 processors. But that's not reusing the block cipher itself.

What must be remembered is that building a hash function out of a block cipher is hard. This is not the same usage context. A fundamental difference is that a block cipher has a key which the attacker does not know (and tries to guess), while a hash function has no secret (when trying to build a collision, the attacker knows everything about every operation in the hash function).