When is it safe to not use authenticated encryption?

What Stephen says in the comment is correct. It is safe to not use authenticated encryption whenever your adversary model assumes that the attacker does not have the ability to manipulate ciphertexts.

  I assumed hard drive volume encryption or per file encryption that is not transmitted over an insecure network should be considered safe to do without a MAC. Is that right?

What if the attacker can install a program on your machine that can modify the ciphertext? It all depends on adversary model.

  The advantage might be that if you do not provide a MAC, an attacker that has gained access to the physical storage and performing a brute force search does not know if they have successfully decrypted the volume/file as they do not have the MAC to verify that the key is correct. Perhaps an attacker could try decrypting and testing if decryption matches English phrases, however there could be multiple keys that produce valid plaintexts.

In practice, for most applications, it will be pretty easy to know when they got the right key. But also, in practice, brute force is not the attack you should be worried about. Very rarely does the attacker attack the cryptography. They usually attack other pieces (password entry, key generation, key storage, side channels, etc) to render the crypto useless.

  What is done in practice, do programs like TrueCrypt or Keepass perform authenticated encryption?

Truecrypt does not provide authenticity and integrity.

It looks like keepass does provide integrity protection, but I couldn't quickly find anything that says exactly how. See the relevant quote from here:

  In repair mode, the integrity of the data is not checked (in order to rescue as much data as possible). When no integrity checks are performed, corrupted/malicious data might be incorporated into the database. Thus the repair functionality should only be used when there really is no other solution. If you use it, afterwards you should thoroughly check your whole database for corrupted/malicious data.


Secure way to store fixed size string of digits

It'll be the same situation that NY City suffered some days ago: when you have little variability on your data, i.e., they have a fixed-small size, it'll always be fast to brute force.

You don't say how long your number is, so I'll assume it can range from 0 - 10,000,000,000 (so, a unique number for each human being on Earth today, plus some spare).  You said that you'll have 9 digits, so anything I say below will be 100 times faster.

In that case, using any kind of hash will only delay the attack by some amount. If you use MD5 hash, some hardwares can calculate 28 Billion hashes/sec.

If you use a unique, random salt for each number, once the attacker finds our the salt (it's not secret, since it's stored in the database), he'll only need to calculate those hashes including the salt, and will take 1 sec for each number you have. No good.

Other hashes (SHA in general, Scrypt, etc and etc) will again slow things down, perhaps requiring more memory, but they won't do magic: in the end it'll be just a matter of time.

And what about changing your digits, for example encoding it so that it'll have letters on it? Still, won't solve your problem, because your data can only have 10 billion variations (in my hipotheses, your case might be even worst).

And what about making another table, with correspondence, that was a proposed solution to the NY City data? Won't do any good to you, since if someone is able to access your number, or their hashes, probably he'll be able to access those data too.

What would I do in your case?

1 - If the data will be inside your system, in your database, and in your company, and not available via web systems: protect as hard as you can using firewalls, blocking who can access the database, scrutiny of your workers, and pray. If some computer of your network is compromised, it might have privileges to access the database, and you're gone.

2 - The data must be exchanged with other systems or other companies: although there are hardware designed to protect data communication (quantum encryption, etc), you'll have to worry about your insiders again, and external attacks on your computers, and the previous scenario still applies.

3 - Does your data really needs to be secret? Perhaps what you can do (or I would do) is nothing. If you have a small number of possibilities for your data, concatenating more information (be it a salt, the email of the user, anything else) won't help, since all that "information" will be stored somehow in your database, or in your code, and will be accessible anyhow.

Protect only the hardware with physical protection (like using HSM) isn't enought. You also need to worry about the ways the application needs to access that information, and in what aspect it would be different if a hacker gained control of one computer inside your company and what he also would be able to do with a keylogger, screenlogger, and so on.


Elliptic curves - operations in larger groups - performance

There are many different flavors of elliptic curves and coordinate systems for them with different costs for computing addition or scalar multiplication.  You can find cost estimates for many of these at the Explicit-Formulas Database (EFD), and measurements from SUPERCOP at https://bench.cr.yp.to/.

Certain curves like Curve25519 in Montgomery form $y^2 = x^3 + 486662 x^2 + x$ were designed to admit fast $x$-restricted scalar multiplication, i.e. to compute $x([n]P)$ given $n$ and $x(P)$, as is sufficient for applications like Diffie–Hellman; software to compute it will consequently run much faster than software to compute scalar multiplication of a generic short Weierstrass curve of comparable size.  Certain curves also admit an Edwards or twisted Edwards form like $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$, which also admits much faster addition formulas than generic short Weierstrass curves, but only those with cofactor at least 4 can have this form.

The cost estimates of the EFD are all written in terms of numbers of additions, multiplications, etc., in the underlying field $\mathbb F_q$.  Certain fields like $\mathbb F_{2^{255} - 19}$ are designed to admit constant-factor speedups for fast arithmetic in software by being just below a power of two, but largely, the number of bit operations to compute addition in $\mathbb F_q$ grows as $O(\log q)$, and to compute multiplication, $O(\log^2 q)$, or $O(\log^{\log_2 3} q)$ if you use Karatsuba's algorithm, etc.

There are no substantive shortcuts around these bit operation costs in general.  Of course, in special cases, curves may admit a fast endomorphism like Koblitz curves, FourQ, etc., which can be used to speed up scalar multiplication on those curves.

Finally, Hasse's theorem bounds the distance between the size $q$ of the underlying field and the size $\ell$ of the group, which is also the size of the scalar ring.  So for larger fields, the scalars may be larger (unless for some reason you're safely working in a subgroup), and to have larger scalars, the field must be larger.  Security is generically limited by the cost $O(\sqrt\ell)$ of Pollard's $\rho$ to compute discrete logs in the group, so if you want Pollard's $\rho$ to cost ${\sim}2^{128}$ bit operations you must choose a group with $\ell \sim 2^{256}$.


What is batching in homomorphic encryption?

In simple terms, batching means "encrypt many messages into a single ciphertext so that one homomorphic operation acts on many messages simultaneously".
This is typically done by representing the message space in a "tuple" format (via an isomorphism).
For instance, by the Chinese remainder theorem (CRT), we know that any tuple
$(m_1, m_2, m_3) \in \mathbb Z_2 \times \mathbb Z_3 \times \mathbb Z_5$
can be written as a single integer $m \in \mathbb Z_{30}$.
Thus, if you have a homomorphic scheme whose message space is $\mathbb Z_{30}$,
we can encrypt tuples
$(m_1, m_2, m_3)$
and each homomorphic operation will actually operate on three values.
In this scenario, you would start from $(m_{1,i}, m_{2,i}, m_{3,i})$,
then obtain $m_i$ via CRT, then encrypt $m_i$ into $c_i$.
Now, if you multiply two ciphertexts $c_1$ and $c_2$ homomorphically,
you obtain an encryption of
$m_1 \cdot m_2 \bmod 30$,
but this is actually equivalent to
$$(m_{1,1}\cdot m_{1,2}\bmod 2,
 \,m_{2,1}\cdot m_{2,2}\bmod 3,
 \,m_{3,1}\cdot m_{3,2}\bmod 5).$$
So, one homomorphic multiplication is multiplying three messages in parallel. Of course, instead of 3, you want a tuple with many entries.
Things work essentially in the same way for polynomials, i.e., you represent a tuple of polynomials of low degree as a single polynomial of high degree, then you encrypt it...


How do fast multiplication algorithms deal with cryptanalysis?

Since Karatsbua is often the default multiplication method for any library with big integers, this is surely used in cryptographic algorithms - whenever large integers are involved. Typical examples for this are RSA, DH key exchange, DSA, all elliptic curve cryptography, etc.

The runtime of Karatsuba depends only on the lengths of the numbers and not on the actual number itself, reducing $n^2$ single-digit multiplications (for long multiplication) to $\approx n^{\log_2 3}$ (exact number depends on the input lengths) and some additions (also only depending on the length of the numbers). So if we can assume constant runtimes for the addition and single-digit multiplication, this should not leak any information. It is just faster.

  do they have any applications for cryptanalysis of asymmetric cryptography algorithms?

I am not sure what you actually mean. Sure, they do have applications: Whenever there is a multiplication of big integers, Karatsuba is used already. But Karatsuba does not give you any other surprising advantage, as far as I know.

  What if we have very fast multiplier?

I don't know why the question i stated in such a hypothetical way, because that is actually how multiplication is realized. For integers, long multiplication is actually the rare case - that's how it is taught in school and mostly used for multiplication by hand.

  How can it help with extracting the secret key from encoded text?

It can't. Actually, I am not sure what you mean with this question. For any state-of-theart encryption scheme with proper parameters, it is practically impossible to extract the key from a ciphertext - if we assume lmitations in time and computation power like "If every atom on earth was a computer and we could use a Dyson sphere around our sun to produce energy until the sun burns out". It is a common misconception, that encryption can actually be broken in such a way.

But coming back to fast multiplication algorithms:  In some cases, other methods like Discrete Fourier transform-based multiplication is used, e.g. this can be used to speed up the Miller-Rabin primality test.


Sharing an encrypted file between a group of people

Yes, you encrypt the file with a symmetric key, then encrypt that symmetric key with each of the recipients public keys. gpg can do this by adding multiple --recipient options.


SHA-256 Hashing problem from binary values

You need to hash exactly 2 bits set to 1. Two bits need to be padded, remembering that this is the last block. In that case the result is correct.

Note that representing two bits with hex value C0 is not correct. C0 represents a full byte and there is no reason to use the most significant bits rather than the lowest significant bits. Two bits set to one should simply be represented as 11 in binary.

I calculated the required result by performing a digest of the value E0 (the value with an additional padding bit set to 1, and the rest 0 valued padding bits: 11 1 0 0000), skipping the usual padding byte 80 (or 1000 0000 in binary), padding with zero valued bytes and then finally setting the (internal, encoded) length to 2. A bit messy, but it works.


Why are the bit lengths of keys and digests equal in Lamport signatures?

The security level of a hash function is determined by its output size. In general, a hash function is considered cryptographically secure when it is collision resistant and provides security level $b = n/2$. Hence, it is not wrong to describe Lamport's scheme that way. However, the description probably was done that way to abstract away some details:

If you want to get $b$ bits security and do a classical message digest, you will need a hash function with $m = 2b$ bit outputs for the digest. However, for the "internal" hash function used to map secret key elements to public key elements you are fine with $n = b$ bit outputs as you just need one-wayness for this function. Now, if you change the message digest to a randomized message digest using $h = H(R,M)$ for randomness $R$ and message $M$, you can get away with $m = n = b$ bit output length for the message digest (if you do everything correctly). This is more about the message digest than about the hash function used inside of Lamport and hence distracting from the actual topic: How does Lamport's scheme work.


Comparison of different asymmetric signatures

In summary: forget the current RSA-512, which is ridiculously vulnerable. For signing QR/2D codes (where minimizing size of the data embedded in the code is essential) with contemporary security:

jump to RSA-2048 using message recovery of ISO/IEC 9796-2, giving a 256-byte 2D-code (including signature) for up to 222-byte useful message, and 34-byte overhead past that mark (but be aware that up to 222-byte of the useful message gets obscured until the signature has been verified);
or, if a 256-byte 2D code is too much and all messages are small (say less than 192-byte message before signature), use Ed25519 or perhaps ECDSA with curve P-256; either adds a 64-byte signature to the message (but has a more complex/power hungry/slower signature verification);
or  venture into relatively uncharted territory and head to the others section, where more compact schemes are discussed.

Also, consider a compact encoding of the useful message (perhaps using data compression), and pay close attention to how the signed message gets transformed into a 2D code: there are several options in format and encoding, and some make 2D code larger thus harder to scan than others.

RSA signature with appendix

Example standards: RSASSA-PSS of PKCS#1v2, ISO/IEC 14888-2 (preview)

Pros:

extremely fast/frugal signature verification (especially with $e=3$);
among the simplest;
widest use and support: this is the signature standard against which all others are compared;
approved by all security authorities.

Cons:

large size in addition to the message, by the modulus size, which is the defining security parameter: RSA-512 (64 bytes added) is trivially breakable with readily available services, RSA-1024 (128 bytes) is rightly considered obsolete, 2048-bit (256 bytes) is the minimum that won't get one shamed;
rather large key size (public key is slightly above signature size for the common format, and can only be about halved; private key is typically larger, that's seldom an issue, and would be fixable);
relatively slow signature generation (a sizable fraction of a second, multiplied by nearly 8 when the key size doubles).

RSA signature with message recovery

Typical standard: ISO/IEC 9796-2 (preview)

Pros:

yields the smallest size added to message (smallest/easiest to read 2D code) when the message is large (wgich is when size matters most): with SHA-256 (128-bit security level), it can be added as little as 256+16 bits or the key size minus that, whichever is larger (e.g. for RSA-2048: 34 bytes added for messages 222 bytes or larger, or whole signed message 256 bytes below that thresold);
about the same extremely fast signature verification (especially with $e=3$).

Cons:

at least some of the message is not in clear (in the 2D code), rather it is recovered by the signature verification process;
presently only common in Smart Cards, and then typically using mode 1 which is rightly frowned at by security certification authorities because it has a security flaw allowing attack in some (mostly theoretical) setups;
not widely supported (e.g. not part of Android, but in BouncyCastle's SignerWithRecovery; discard mode 1/ISO9796d2Signer in favor of mode 2 or 3/ISO9796d2PSSSigner for new applications);
same large large key size and slow signature generation;
not FIPS-compliant (but Common Criteria recognized).

Rabin/Williams (RW) variants of the above two

Example standards: ISO/IEC 14888-2, ISO/IEC 9796-2.

Pros:

even faster signature verification (nearly twice as fast as RSA with $e=3$), which is good for some very low end/power starved devices.

Cons:

more tricky signature process (a common implementation computes a Jacobi symbol, and an error there can destroy all security; as pointed in comment by Squeamish Ossifrage, there is however an alternative);
uncommon, seldom any security-certified device available to sign.

DSA

Example Standard: FIPS 186-4 section 6.

Pros:

smaller size added to message than RSA with appendix, and than RSA with message recovery for small message (only): with SHA-256 (128-bit security level), 64 bytes added regardless of message size (thus smaller 2D code than RSA signature with message recovery for messages below some threshold like 192 bytes, but like 30-byte larger for large message).
possibly faster signature generation than RSA, especially at larger security level;
well standardized in FIPS 186-4.

Cons:

slow signature verification compared to RSA (can by a factor well over 100 compared to RSA with $e=3$);
about the same large public key size as RSA;
failure of RNG on the signer side can be disastrous.

ECDSA

Example standards: FIPS 186-4 section 9, ANSI X9.62, Sec1v2+Sec2v2

Pros:

same small size added to message as DSA;
signature generation faster than RSA (by a factor like 10 and growing with security level);
signature verification and generation appreciably faster than DSA (by a factor like 20 and growing with security level);
small public key size (about the same as signature in a common variant);
same small private key size as DSA (e.g. half of signature);
has gained traction over DSA, thanks to the above and to NIST support.

Cons:

verification still much slower/more power hungry than RSA or RW;
more complex math and larger code than RSA or DSA;
many incompatible curves and formats around (though P-256/secp256r1 is a common choice for curve);
some variants/implementations may arguably have been patent-encumbered, or even could still be;
failure of RNG on the signer side has same disastrous effect as for DSA.

EdDSA

Example standards: RFC 8032, Ed25519

Pros:

same small size added to message as DSA/ECDSA;
amenable to faster implementation than ECDSA for signature generation and verification, especially for software implementations of signature generation that must resist side-channel attacks;
well-accepted and available in open source software;
signature does not require a RNG, thus can't fail for that reason;
stays relatively clear from a patent minefield.

Cons:

verification still sizably slower/more power hungry than RSA or RW;
not validated by FIPS or AFAIK by other governmental security authorities.

Others

Schnorr signature with appendix has existed for a long time and is academically well recognized, but seldom used. The original variant has a signature 25% shorter than (EC/Ed)DSA, and stands unbroken, but has no security reduction (contrary to variants with the same size as DSA), and (I guess, thus) is not standardized. EC-Schnorr exists (in all too many incompatible standardized versions, including EdDSA).

There are message-recovery variants of (EC)DSA and Schnorr signature (bibliography there), which save 25% in size (perhaps 50% which put them on par with RSA using message recovery, but apparently at the cost of giving up security reduction). They are great for QR codes conveying little data. Among these, I regard ECPVS of ANSI X9-92-1, which was developed for stamps, as among the closest to a practical and recognized standard (but it appears to be patented, at least in some implementation variants).

The most compact signature scheme with appendix might be Boneh–Lynn–Shacham but it is complex, verification is slow, there is no consensus on choice of secure parameters for compact variants (some formerly considered secure no longer are), and I can point a single use case (with, I'm afraid, marginal security by today's standards).


A solution is given by Peter Ryan, Crypto Santa.  In The New Codebreakers, vol. 9100 of Lecture Notes in Computer Science, pp. 543-549, Springer, 2016. http://dx.doi.org/10.1007/978-3-662-49301-4_33

An earlier version (with Sjouke Mauw and Sasa Radomirovic) can be found at http://hdl.handle.net/10993/25936 (Open access), Security protocols for Secret Santa.


Are these two methods of differential cryptanalysis different?

The approach in the Heys’ tutorial where the author uses the approach

bruteforce last round using every possible keybit [at the output of] active sboxes and trace differentials up to [the output of] $r-1$ rounds

is more fundamental because it is more general.
One needs to meet in the middle at the output of some round and check which value for the guessed keybits results in the highest probability differential for the set of plaintext/ciphertext pairs with a fixed input difference.
It is most convenient and natural to use meet in the middle at the input to the last round, and let the guessed key bits be the bits from the last round.
In fact the other (amazing king) reference is essentially using the same approach (whether the author of the webpage realizes it) since that is a one round cipher with $r=1,$ so $r-1=0,$ and the $r-1$ differential is the input (plaintext) difference.


What are the differences between proofs based on simulation and proofs based on games?

As the other answers already state here, game-based definitions are easier to write proofs for, but simulation-based definitions are often clearer in terms of the security guarantee that you get. The best example of this is IND-CPA (game-based definition) versus semantic security (simulation-based definition). Note that IND-CPA is really not a convincing definition: why does not being able to distinguish between an encryption of 2 ciphertexts guarantee that you can't learn any partial information? It is only once you prove equivalence to semantic security that it becomes clear (both because semantic security is clear, and because the proof of equivalence is very illuminating).

Unfortunately, in most cases, the game-based and simulation-based definitions are not equivalent. So, which is better? It depends on the situation. However, there is one very important thing that simulation gives you that game-based definitions do not, and that is security under composition. The stand-alone simulation-based definitions give you security under sequential composition, and universal composability and its variants give you security under concurrent composition. Note, that this security is not only concurrent executions of the same protocol (since this is also often guaranteed in a game-based definition), but concurrent executions with arbitrary other protocols. This is not guaranteed by any game-based definition (to the best of my knowledge). Even when considering the stand-alone definition, it is much easier to plug your protocol into something larger and prove its security, using the modular sequential composition theorem. In short, these composition theorems let you analyze a larger protocol while relating to the subprotocol as an ideal functionality call. This greatly simplifies things.

I believe that simulation-based definitions are qualitatively better, in most cases. The guarantees are clear and composition is guaranteed. This does not mean that game-based definitions are not good, and in fact, they are often the way to go (especially for lower-level primitives). But, it really depends on the case.

I have written a tutorial on how to write simulation proofs. This should help.


Polynomial multiplication and division in $2^{128}$

The RELIC library has support for binary fields. Check the functions fb_inv_exgcd for inversion and fb_mul_lodah (which calls fb_muln_low and fb_rdcn_low) for multiplication. There is even a ATMega128 backend written in assembly, though it does not support 128-bit fields (but should give you a head start if you need to write it).

You will need to make a few adjustments in order to isolate the multiplication code, but it shouldn't be too hard. Or you can simply use the library as is.

(Disclosure: I'm one of its developers)


How can I make sure non-open source programs are really using end-to-end encryption?

Is there's a way to make sure that non-open source programs are really using end-to-end encryption?

Only by deep reverse-engineering. Which is hard, and might be illegal. Plus the apps are a moving target: they change like weekly. And, using end-to-end encryption is not proof that no interception is possible: this encryption (or its key generation) could be weak, accidentally, deliberately, perhaps surreptitiously. In the end, there's no practical way¹.

True story: I was the lead engineer for this² modem capable of end-to-end encryption with negotiation of session keys using Smart Cards, released in 1990, sold in France with some success. A director of our company insisted that we get approval from the authorities for these features, because that was raised in a conversation with Apple France, our main distributor. Soon after (mid 1991) I had a guy introducing himself with a military rank in my office, explaining that the law required that for crypto devices sold to the general public, there must be a way to find the key with a test requiring at most 240 steps. He required a detailed description of the protocol. I argued that changing it would break interoperability. The guy proposed addition of a side channel leaking the session key, so that if one end was using the rigged device, the session key would be available for one intercepting the line signal and knowing the method. I had the distinct impression this was standard procedure. In the end, I created a new packet type that older devices ignored, containing the session key RSA-encrypted, sent at moreless regular intervals, and new models did that. I remember the guy came for a demo. I insisted not to know the production private key, for my own safety. I still have the source code for that device, in 8051 assembly.

Note: the main feature of that device's point to point crypto was that, when you had made a set of Smart Cards, and inserted one in your modem, you could be confident that only someone holding another Smart Card from the set could connect. This feature was not compromised, as French law did not ask.

¹ No practical way to be confident that there is effective end-to-end encryption. It's sometime possible to prove that there is no end-to-end encryption. For example, if data goes thru a central server thru a https link protected using a server certificate, and the user messages are revealed by breaking that https encryption using a local proxy (a standard hack on one's device), then we are sure there is no end-to-end encryption.

² Scroll down and click on the wide picture or right arrow for more, including internals.I have no connection with this website.


Yes.

There has been a lot of work on "proof of work" protocols or "time-lock puzzles." Typically in cryptography, functions are either easy to compute or intractable. These protocols look at functions that are moderately hard to compute.

To do time-release encryption, you need a puzzle with the following properties:

Difficulty of the puzzle can be monotonically increased according to some difficulty parameter
Best algorithm to solve it is intrinsically sequential (parallel computing doesn't help)
Amortized cost of solving a group of puzzles is the same as a single puzzle
There is a trapdoor (shortcut) that allows efficient evaluation of the puzzle

With time-release crypto, the idea is to generate a puzzle that will take a certain amount of time to solve based on an estimate of a person's computational power and how it will grow in the future (e.g., Moore's law). As you can tell, it only gives you a fuzzy indication of how long it will stay secret (see below for a real world example). Property 2 is very important because adding parallel computation is easy and it is hard to estimate how much parallelization is possible.

Note that most proof of work protocols do not care about property 2 because they are used in different ways. These might be based on finding partial collisions/preimages in hash functions or exhaustive search of a small space (e.g., bitcoin), however speedups with parallel computing is trivial in these examples. There are also a number of memory-based puzzles that require lots (more than can be cached) of memory accesses, which is a more predictable measure of time on computers.

Back to time-release crypto. The idea is to instantiate a puzzle $p$ with difficulty $d$: $p=\mathsf{Puzzle}(d)$. A trapdoor $t$ for efficiently solving it is known to the person who generates the puzzle. This person then encrypts her message under key $k$ with a normal encryption function: $c_1=\mathsf{Enc}_k(m)$. She then release an "encryption" of the key she used by combining the key with the solution to the puzzle. Note that she can efficiently solve the puzzle with trapdoor $t$ but the recipient can't. She computes: $c_2=k \oplus \mathsf{Solve}_t(p)$. The ciphertext is $c_1,c_2$ plus a description of the puzzle.

To decrypt, the recipient computes $s=\mathsf{Solve}(p)$, which should take a moderate amount of time. He then recovers the key by $k=c_2\oplus s$, and can then decrypt $c_1$.

The disadvantage to time-release cryptography is that the recipient must devote an entire processor to solving the problem for the period of time that it should remain secret.

The best proposal for a Puzzle with the right properties is due to Rivest, Shamir and Wagner in this paper. It is based on repeated squaring in RSA groups. A recent result precludes any intrinsically sequential time-lock puzzles in the random oracle model (e.g., based on hashing).

In 1999, Rivest created a time capsule message to commemorate the 35th anniversary of MIT's Laboratory for Computer Science. He talks about how he designed it to require 35 years to decrypt. It is an interesting read.


How do you make Fermat's primality test go fast?

I'm not very good at reading Lisp, so please correct me if I'm wrong, but it looks as if you're naïvely calculating $a^{n-1} \bmod n$ by first raising $a$ to the $n-1$ -th power, and then reducing the result modulo $n$.

This is a very inefficient way to implement modular exponentiation since, as you've noticed, the intermediate result $a^{n-1}$ can quickly grow to an enormous size.  It is far more efficient to reduce any intermediate results modulo $n$ while raising $a$ to the $n-1$ -th power, effectively doing the calculation directly in the ring $\mathbb Z / n \mathbb Z$ of residues modulo $n$.

Unfortunately, I don't know enough Lisp to directly suggest an efficient implementation of modular exponentiation for you, but the Wikipedia page I linked above does describe some suitable algorithms, and provides some iterative pseudocode implementations that you may be able to adapt.


Per the standard definition, a negative quantity is always negligible. This does not matter, however, because when a definition demands that a quantity be negligible, that quantity is virtually always non-negative (e.g., a probability or an absolute value).


Can I use a random number generator with seed for key derivation?

My question is: can I use a random number generator that works with seeds?

Yes.

All you need is a 256-bit uniform random secret, or a seed chosen by a process with 256 bits of min-entropy.  You can derive everything else from there using a key derivation function like HKDF-SHA256, which is—securitywise—just a kind of PRNG with a convenient API to name what the purpose of each derived key is so that you can reproduce the computation.

For example, you could ask a computer to generate for you a 20-word diceware phrase $p$.  You can convert it into a 256-bit effectively uniform random secret $k$ with $\operatorname{HKDF-Extract}(p)$; then, from $k$, you can derive:

an AES-GCM-256 key for notes in a private todo list with $k_1 = \operatorname{HKDF-Expand}(k, \text{‘todo list key 1’})$
an ECDSA key for a Bitcoin wallet with $d = \operatorname{HKDF-Expand}(k, \text{‘Bitcoin wallet, 2019-03-23’})$
an RSA key using a particular prime generation procedure with a particular choice of PRNG seeded with $s = \operatorname{HKDF-Expand}(k, \text{‘my RSA key seed’})$.  Of course, RSA key generation is rather slow!  So people don't usually do this.

There are two key points:

You must let a computer or fair dice rolls choose the phrase $p$ for you, and then commit it to memory.  Don't try to think of $p$ yourself first, because you are bad at thinking randomly.
The labels must all be distinct.  All bets are off if you use the same label for two different purposes.


Understanding pseudo-random functions (used in a Oblivious Transfer Protocol)

Yes, if you take an instance out of the function family (e.g. $F_{K_1}$), then the evaluation of this function at $x$ always yields the same result. You can think of it like that:

If you fix a key $K$, then your PRF is basically a look-up-table. For every possible input $x \in \{0,1,\cdots,2^m-1\}$ there is an entry in the look-up-table for the output $F_{K_1}(x)$. For each key, there exist a different look-up-table.

So why is called pseudo random? Well imagine some bad guy who sends different $x$ to a black box and gets back some value. Inside the black box, there is either a $F_{K}$ with a key $K$ chosen uniformly at random or a function $f: \{0,1\}^m \rightarrow \{0,1\}^m$ that is chosen uniformly at random from the set of all possible functions from $\{0,1\}^m$ to $\{0,1\}^m$. If the bad guy cannot tell wether he is talking to $F_K$ or $f$, then $F$ a good PRF, because the output looks totally random to him in either cases.

There is a possbile way to distinguish both functions, if the bad guy accidentally finds two distinct values $x_1, x_2$, that yields the same output $f(x_1) = f(x_2)$. Then he knows, that he's talking to $f$. But if $m$ is suffienciently large, the probability of a collision is very low.


Assuming that someone discovers your encrypted PINs, knows about your algorithm, but does not know $n$ or $k$, then it is more secure than if they discovered the plain PINs. As you normally only get a few attempts at guessing a PIN

However, there are some features of your algorithm that make it less than perfectly secure.

If you replaced the expression $n(k+n)$ with just $k$, and memorised a different four digits for $k$ for each PIN to encode, then what you would have is a one time pad. This is perfectly secure, but you have gained very little - you may as well remember the PINs. It might be relevant though if you needed to send a new PIN to someone else in future, but could only communicate privately and securely beforehand. So you could agree a value of $k$ in private then send the encrypted PIN safe in the knowledge that to an observer not knowing $k$, the real value of the PIN could be anything.

The security of re-using your value of $k$ depends on the behaviour of $n(k+n)$ mod $10$ with different $n$. Immediately we can see a problem - when $n$ is $0$, the output is the original PIN. Therefore using $n=0$ is out. Other values of $n$ have a more subtle problem - several of them do not cover all possible variations, $n=5$ for instance only gives 16 variations of $n(k+n)$ mod $10$ for a 4-digit PIN, so if an attacker knew or guessed $n=5$ they would have a good chance of guessing the original PIN without needing to know $k$. The "bad" values of $n$ for you are anything which shares a common factor with $10$. The "good" values are therefore $[1,3,7,9]$

So your algorithm can in theory protect four PINs reasonably well? Sort of, there is one more problem. The algorithm is easily reversible, therefore if somehow an attacker learned one of your PINs, they would be able to figure out 4 potential values of $k$ and only need 12 guesses (different values of $n$ and $k$ that still work) to figure out the next PIN. Then only 2 for the third one, and immediately get the fourth.


Possible SHA-256 implementation weakness

Quoting zaph from the comments:

  If the implementation does not produce the correct results it is a failed implementation, don't use and report it.

This is pretty much the correct course of action, assuming that the algorithm is supposed to be SHA-256.

Cryptanalysis of the incorrectly implemented algorithm would be non-productive, unless your goal is to maliciously exploit the protocol that is using this hash function.

Alternatively

It is possible that the author was attempting to be clever or obscure and made such a modification intentionally. There may not be much you will be able to do to help the situation if that is the case; Even if you present collisions/preimages, you may simply garner hostility from the author/users (see the drama around IOTA for an example).


Does Identity-Based Encryption actually solve any problem?

IBE is advantageous over standard asymmetric methods in one aspect, and that doesn't appear to apply in the case you're interested in.

In both cases, IBE and asymmetric methods require an enrollment process (whether to distribute secrets, or authentication data), so there's no real difference there.

However, when Alice wants to send a message to Bob, with standard asymmetric cryptography, Alice and Bob needs to exchange messages (whether to perform a DH exchange, or for Bob to send Alice his certificate).  In contrast, with IBE, Alice just encrypts the message with Bob's public id, and sends that message to Bob; Bob doesn't need to send a message to Alice.

So, that is the advantage of IBE; if you are sending unidirectional messages, you don't need a back channel to complete the exchange.  If this is important for you (for example, if you are sending encrypted emails; the store-and-forward email architecture doesn't allow a back channel), this is quite useful.  If you do have a convenient back channel (as in your case; you're going to exchange messages encrypted with a symmetric key anyways), it doesn't gain you anything.


Use of less than secure random numbers for 'a' during an SRP proof of password

It seems like a better solution would be to have the server that is providing the Javascript file, also provide a random seed.  The Javascript can then use that random seed (and anything other maybe-random bits it can scrounge up, such as the output from Math.random()) to see a cryptographic PRNG, and then use the output of that crypto-PRNG for generating s, a, b.  After all, the server who sends you the Javascript has to be trusted anyway, so you might as well trust it to give you some random numbers, too.

See https://security.stackexchange.com/a/34425/971 for more on this.


Well, $f$ is assumed to be a one-way function. That means, there cannot exist an efficient algorithm for finding preimages under $f$. The algorithm $A'$ is what we call a reduction.

We are trying to show that an efficient algorithm for attacking the signature scheme does not exist. To do that, we assume the contrary, i.e. we assume an efficient algorithm $A$ exists that successfully forges a signature. We then use this algorithm $A$ as blackbox (i.e. we do not assume anything about it beyond the fact that it works) to construct a second algorithm $A'$.
This algorithm can efficiently compute preimages under $f$, if $A$ works as specified. Because we assumed that $f$ is one-way, this a contradiction, as no such algorithm can exist if $f$ is one-way.

Now, because the existence of $A$ implies existence of $A'$, but $A'$ cannot exist, we can conclude that $A$ cannot exist either. This proves that no efficient adversary against the one-time signature scheme exists and the scheme is, therefore, secure.

Some algorithm for inverting $f$ that does not use the adversary against the signature scheme (besides not being efficient) would not allow you to conclude anything about the security of the scheme.


How are these AES MixColumn multiplication tables calculated?

It looks like those are just precalculated tables for multiplication by the constants 2, 3, 9, 11, 13 and 14 in the AES finite field.  We already have several questions about how multiplication in finite fields in general, and in the AES representation of GF(28) specifically, is done, such as:

Galois fields in cryptography
How is multiplication in field $GF(2^{8})$ done?
How to optimise a finite field multiplication?
How to do Hexadecimal multiplication in GF(2^8)

and even:

Efficient pen-and-paper calculation of the Galois Field multiplication?

That said, I would not recommend using lookup tables for these multiplications at all, since they can be easily calculated at runtime.  Not only do lookup tables introduce the risk of timing attacks and other side channel attacks (since memory lookups don't always run in constant time), but they are also often less efficient than calculating the multiplication directly, both on high-end CPUs (where memory access is relatively slow) and on low-end microcontrollers (where memory itself is often a scarce resource).

The usual way to do multiplication in GF(2n) is using the double-and-add algorithm, also known as "Russian peasant multiplication", which uses only two primitive arithmetic operations:

addition, which in GF(2n) is simply bitwise XOR, and
doubling, i.e. multiplication by 2 (or by $x$, in the polynomial representation), which requires a left shift followed by a polynomial modular reduction, and can be efficiently implemented e.g. like this in C:

static inline uint8_t dbl(uint8_t a) {
    return (a << 1) ^ (0x11b & -(a >> 7));
}

Both of these operations can be fairly easily implemented without branches or table lookups, which means they can be usually expected to run in constant time (although one must, of course, always watch out for possibly compiler and/or CPU optimizations that could reintroduce data-dependent timing variations).  Using these primitive operations, we can write a general AES finite field multiplication routine e.g. like this:

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0;
    while (b > 0) {
        p ^= a & -(b & 1);         /* add a to p if the lowest bit of b is set */
        a = dbl(a);                /* multiply a by 2 in the finite field */
        b >>= 1;                   /* shift the next bit of b to the lowest position */
    }
    return p;
}

Note that the running time of the code above depends on b, and specifically on the position of its highest set bit, but (hopefully, assuming a reasonable compiler and CPU) not on a.  If we wanted, we could also make the timing fully independent of b by replacing while (b > 0) with a fixed 8 iteration loop such as for (int i = 0; i < 8; i++), but this isn't really needed if b is a public constant.

However, for multiplication by a constant b, we don't really need this general routine at all; knowing the value of b, we can manually unroll the loop and eliminate any steps we know are not needed, leaving just e.g.:

uint8_t mul2(uint8_t a) {
    return dbl(a);
}
uint8_t mul3(uint8_t a) {  /* 3 = 2 + 1 */
    return dbl(a) ^ a;
}
uint8_t mul9(uint8_t a) {  /* 9 = 8 + 1 */
    return dbl(dbl(dbl(a))) ^ a;
}
uint8_t mul11(uint8_t a) {  /* 11 = 8 + 2 + 1 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a2 ^ a;
}
uint8_t mul13(uint8_t a) {  /* 13 = 8 + 4 + 1 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a4 ^ a;
}
uint8_t mul14(uint8_t a) {  /* 14 = 8 + 4 + 2 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a4 ^ a2;
}

Also note that, for AES (Inv)MixColumns, you're going to need to multiply each input byte by four different constants in a specific pattern and sum (i.e. XOR) the results.  It's possible to do this more efficiently by splitting the finite field multiplications into doublings and XORs and applying the distributive law dbl(x) ^ dbl(y) == dbl(x ^ y), e.g. like this:

void mix_columns(uint8_t cols[4]) {
    uint8_t a = cols[0], b = cols[1], c = cols[2], d = cols[3];
    cols[0] = dbl(a ^ b) ^ b ^ c ^ d;  /* 2a + 3b + c + d */
    cols[1] = dbl(b ^ c) ^ c ^ d ^ a;  /* 2b + 3c + d + a */
    cols[2] = dbl(c ^ d) ^ d ^ a ^ b;  /* 2c + 3d + a + b */
    cols[3] = dbl(d ^ a) ^ a ^ b ^ c;  /* 2d + 3a + b + c */
}

void inv_mix_columns(uint8_t cols[4]) {
    uint8_t a = cols[0], b = cols[1], c = cols[2], d = cols[3];
    uint8_t x = dbl(a ^ b ^ c ^ d), y = dbl(x ^ a ^ c), z = dbl(x ^ b ^ d);
    cols[0] = dbl(y ^ a ^ b) ^ b ^ c ^ d;  /* 14a + 11b + 13c + 9d */
    cols[1] = dbl(z ^ b ^ c) ^ c ^ d ^ a;  /* 14b + 11c + 13d + 9a */
    cols[2] = dbl(y ^ c ^ d) ^ d ^ a ^ b;  /* 14c + 11d + 13a + 9b */
    cols[3] = dbl(z ^ d ^ a) ^ a ^ b ^ c;  /* 14d + 11a + 13b + 9c */
}

(Online demo with self-test.)

Further performance improvements may be possible e.g. through the use of bitslicing techniques.


In RSA, why would we ever want to find the values of p and q if we already know phi(n)?

From an attacker's perspective, when we have $(n,e)$ and $\phi(n)$, we can compute a working $d\gets e^{-1}\bmod\phi(n)$. It will allow decryption or signature forgery in time polynomial to $\log(n)$: the attacker thus has won. Yet for repeated decryption or signature, the attacker may want to use the Chinese Remainder Theorem for efficiency, just like some legitimate users of RSA routinely do (see next section), which requires factoring $n$.
Also, the attacker might want to look at what the factors of $n$ are in hope to find patterns, in order to carry more attacks for other keys generated by the same method. And as kelalaka puts it, mathematical enthusiasm, curiosity, and searching for where that leads for better understanding are reasons enough.

The Chinese Remainder Theorem to speed-up RSA
A pragmatic reason both legitimate users of RSA and attackers want the factors of $n$ is they allow computation of the private-key function $x\mapsto y=x^d\bmod n$ several times faster using the Chinese Remainder Theorem.
When $n=p\,q$ with $p$ and $q$ distinct primes, that goes:

precomputations done once:

$d_p\gets e^{-1}\bmod(p-1)\;$ or equivalently $\;d_p\gets d\bmod(p-1)$
$d_p\gets e^{-1}\bmod(q-1)\;$ or equivalently $\;d_q\gets d\bmod(q-1)$
$q_\text{inv}\gets q^{-1} \bmod p$

for each computation $y\gets x^d\bmod n$ :

$\;x_p\gets x^{d_p}\bmod p$
$\;x_q\gets x^{d_q}\bmod q$
$\;y\gets\big((x_p-x_q)\,q_\text{inv}\bmod p\big)\,q+x_q$

The execution time is dominated by steps 1 and 2. The cost of exponentiation modulo $m$ with the exponent the same size as $m$ grows about as $(\log m)^\alpha$ with $2<\alpha\le3$ (depending on arithmetic algorithms used for modular multiplication), and using the CRT roughly halves $\log m$. Thus (for large $p$ and $q$ of comparable magnitude) the work is reduced by a factor in the order of $3$ (obtained as $2^\alpha/2\,$). Also, it is possible to parallelize steps 1 and 2, further halving the wall clock time on a machine with two otherwise idle CPUs.
The technique is even more useful if $n$ has more than two prime factors, that's multi-prime-rsa. For the disputed history of that realization, see this. For the computations, see this.
It is not uncommon that software accepts a private key as $(n,e,d)$ yet use that speedup, in which case it will need to factor $n$, as follows.

Getting the factorization of $n$ from $(n,e,d)$ or $(n,\phi(n))$
When given $(n,e,d)$, we can factor $n$, but the usual method for this does not find $\phi(n)$ first, for that's not trivial. Sure, computing $(e\,d-1)/\left\lceil(e\,d-1)/n\right\rceil$ can yield $\phi(n)$ if $e$ is small and $d$ was computed as $d\gets e^{-1}\bmod\phi(n)$. However, neither condition is required by the modern definition of RSA¹.
The method generally used to factor $n$ from an RSA $(n,e,d)$ or $(n,\phi(n))$ computes $f\gets e\,d-1$ or sets $f\gets\phi(n)$, then uses that for any $w$ coprime with $n$, if holds $w^f\equiv1\pmod n$. The factorization of $n$ is possible using an algorithm in Gary L. Miller's Riemann's hypothesis and tests for primality, in Journal of Computer and System Sciences, 1976 (free PDF available). For odd composite square-free $n$, that goes:

$r\gets 2f/(f\oplus(f-1))$ [this $r$ is odd and such that $f=r\,2^s$ for some $s$]
repeat (few times, since each iteration succeeds with probability better than 50%)

draw a random integer $w$ in $[2,n-2]$
optional (and not useful for $n$ an RSA modulus)

$u\gets\gcd(w,n)$
if $u\ne1$

output "$u$ is a non-trivial factor of $n$" and stop.

compute $v\gets w^r\bmod n$
if $v\ne1$

while $v\ne1$ (that's at most $s$ times)

$u\gets v$
$v\gets v^2\bmod n$

if $u\ne n-1$

$u\gets\gcd(u+1,n)$
if $u\ne1$

output "$u$ is a non-trivial factor of $n$" and stop.

When $n$ has more than two factors, the algorithm can be used to fully factor $n$, by running it again replacing $n$ by $u$ or $n/u$, for any of these two that is not prime. We have not handled some tractable difficulties arising when $n$ is divisible by the square of a prime, but that's not the case in standard RSA.
Try It Online! This generates an $(n,e,d)$ with 2048-bit $n$ the product of two large distinct primes $p$ and $q$, and $\gcd(p-1,q-1)$ with a 256-bit prime factor, a large random $e$, and large $d$ with $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$ [which makes computing $\phi(n)$ non-iteratively impossible AFAIK]; then finds the factorization of $n$ by Miller's algorithm.

¹ The de-facto definition of RSA is PKCS#1. It prescribes $e\in[3,n)$, $d\in[1,n)$, and $e\,d\equiv1\pmod{\lambda(n)}$. This uses the Carmichael function $\lambda$. When $n=p\,q$ with $p$ and $q$ distinct primes, it holds $\lambda(n)=\operatorname{lcm}(p-1,q-1)=\phi(n)/\gcd(p-1,q-1)$. Using $\lambda$ (rather than $\phi$) makes the later equation the necessary and sufficient condition (rather than a sufficient but not necessary condition) for RSA encryption/decryption to succeed for any message in $\Bbb Z_n^*$, and in the whole $\Bbb Z_n$ when $n$ is squarefree. Using $\lambda$ allows at least $\gcd(p-1,q-1)$ working private exponents $d$ values, of the form $d_j=(e^{-1}\bmod\lambda(n))+j\,\lambda(n)$. That's at least two, and can be many (though rarely for random choice of primes $p$ and $q$). The FIPS 186-4 standard requires using $d_0$, which is often smaller than $e^{-1}\bmod\phi(n)$, often making raising to the power $d$ faster.


Two working decipher keys giving various, valid results for one ciphered message - is it possible?

This property can be achieved with a One-time pad.

  "In fact, it is possible to "decrypt" out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext that will allow Eve to choose among the various possible readings of the ciphertext."

This is nicely shown in this example from Wikipedia (section "Attempt at cryptanalysis").


How to distinguish a transposition cipher from a simple substitution cipher only given a ciphertext?

Think about what properties of the plaintext are preserved by the candidate ciphers. You want to look for those patterns.

Transposition moves letters around but keeps their identity. Substituting keeps positioning but changes identity.

So, you can do a test for whether letter identity is preserved.

The easiest is to do a frequency analysis: if your common letters (e, t, etc) are still common, you probably have a transposition. Of course if not, you are half way to breaking the substitution!

A bonus test goes the other way: see whether position is preserved. A perfect transposition will shuffle the letters, so no pairs should come up more often than expected by chance. If there are any weirdly frequent letter pairs, those are evidence that you have a substitution cipher.


Securely re-using a shared key with NaCl

Is this concern addressed by the presence of the nonce in nacl.secretbox(message, nonce, key) thus making it safe to re-use the shared secret key as long as the nonce is different every time?

Yes. But you still have to be careful about protocol level attacks, such as replays or re-ordered messages.

  (which is a requirement anyway obviously).

Note that a nonce doesn't need to be unique by itself, it's only the key-nonce pair that needs to be unique. For example if you use a per-connection key you can use a simple counter as nonce, since each connection has a unique key.

  Would it be even safer to derive a unique shared key for each message by hashing some salt and sending the salt along with each message so that the other side can do the same to obtain the unique shared key for the message? Or is this redundant?

That's unnecessary if 24-byte nonces are sufficient for your purpose.

Internally xsalsa20 hashes a 32-byte key together with the first 16 bytes of the nonce into a 32-byte key, which is then used together with the remaining 8 bytes of the nonce.


You want a pair of functions $(f_1,f_2)$ from a set $S$ of possible passphrases to a key set $K$, that is $f_1,f_2: S \rightarrow K$. The functions are public, in the sense that they can be computed by anyone.

Your security goal is that the cost of finding $f_2(pw)$, knowing $f_1(pw)$, should be roughly as expensive as finding $f_2(pw)$ by searching for $pw$, using $f_1(pw)$ to confirm a correct guess, then simply computing $f_2(pw)$.

In this setting, using a sensible KDF is the best you can hope for. You compute a long bit string $s = \mathit{KDF}(pw)$. The string splits into two parts, $s = s_1 || s_2$, and $f_1(pw) = s_1$, $f_2(pw) = s_2$.

It is good because: Under reasonable assumptions (the KDF looks like a random function). If the KDF looks like a random function, then unless you know the input to the function, you cannot use part of the function value to say something about any other part of the function value.

It cannot be improved upon because: The requirement that $f_1(pw)$ should contain as much entropy as $pw$ means that the function value $f_1(pw)$ more or less uniquely determines $pw$, which means that exhaustive search will work.

Trivial remark on the proposed solution: We could have said that $f_i = \mathit{KDF}(pw, i)$, in line with your HMAC proposal, but then in practice the workload for someone trying to confirm a guess is half that of the legitimate user. With the above proposal, the workloads are equal.


Block cipher's output in case of uniformly drawn input

The answer is yes.
While I can't provide a rigorous proof (because I don't know for now how to make one for such distributions), I can give an intuitive argument, which you can formalize I hope.

The main reason is simple: $E_k$ is a permutation for all choices of $k$.
This means that essentially all the encryption function does is "re-label" the given input message, there are no collisions (which would change the distribution) and input- and output space are equal in size so, every value in the input space is mapped to precisely one value in the output space and vice-versa.

So if you have probability $1/2^n$ of drawing $m$ you have probability of $1/2^n$ of ending up with $E_k(m)=c$ and so $c$ is distributed uniformly at random.


One way to try tackling simpler problems like this is by writing them out as equations and doing algebra on them.  In this case, let's take this statement from your comment with the answer:

  The opponent can now concatenate the new message, which consists of $Y_1 || \dots || Y_m$ with the original MAC to form a message that will be accepted as authentic by the receiver.

So this is saying that the following equation is true:

$$
C_k(Y_1 || \dots || Y_m) = C_k(X_1 || \dots || X_m)
$$

But is it really true?  One way we can test this is by using the laws of equations (like in algebra) to rewrite this one over and over and see if it has the same truth value as some other equation that we can independently tell is true.

By applying the definition of $C_k(M) = E_k(\Delta(M))$ to both sides of the first equation we get:

$$
E_k(\Delta(Y_1 || \dots || Y_m)) = E_k(\Delta(X_1 || \dots || X_m))
$$

And since the function $E_k$ is a block cipher, it has an inverse $D_k$, which by applying to both sides we can get this:

$$
\Delta(Y_1 || \dots || Y_m) = \Delta(X_1 || \dots || X_m)
$$

Applying the definition of $\Delta(M)$ to both sides we get:

$$
Y_1 \oplus \dots \oplus Y_m = X_1 \oplus \dots \oplus X_m
$$

So the attack that you've quoted in your comment hinges on the fact that it must somehow cause this equation to be true.  Your comment explains the attack as this (I've corrected a notational error):

  The opponent can attack the system by replacing $X_1 || \dots || X_{m-1}$ with any desired values $Y_1 || \dots || Y_{m-1}$ and replacing $X_m$ with $Y_m$ where $Y_m$ is calculated as follows: $Y_m = Y_1 \oplus \dots \oplus Y_{m−1} \oplus \Delta(M)$.

Let's try substituting that for $Y_m$ in the equation:

$$
Y_1 \oplus \dots \oplus Y_{m-1} \oplus (Y_1 \oplus \dots \oplus Y_{m−1} \oplus \Delta(M)) = X_1 \oplus \dots \oplus X_m
$$

XOR is an operation where every element is its own inverse, so $Y_i \oplus Y_i = 0$ which is the identity element.  It's also an associative and commutative operation, so in the left side of this equation we can cancel out all of the $Y_i$ terms, and we get:

$$
\Delta(M) = X_1 \oplus \dots \oplus X_m
$$

Which is nothing other than the definition of $\Delta(M)$, which we were given as a premise.  So the technique you cited is guaranteed to forge a message and its tag different from $M$.  Worse, it allows the adversary to pick any values they like for $Y_1$ to $Y_{m-1}$.

The short, intuitive summary of that is that the problem with this MAC is that the way the $\Delta(M)$ it combines the plaintext message blocks with XOR gives the attacker way too much latitude.  Given any message $M$, it's trivial for the attacker to compute $\Delta(M)$, as well as many, many ways that they can compute a message $M'$ such that $M ≠ M'$ but $\Delta(M) = \Delta(M')$.  And since the MAC is just the deterministic encryption of $\Delta(M)$, that guarantees a successful forgery.


You are right. And this had been exploited in the past in the PS3 and Bitcoin wallet events.

The first half of the signature is the x coordinate of $k \times G$, and $k$ is the ephemeral key that must be unique to each signature generated. If it's static then the following formula would recover the private signing key:

$k = {{z_1 - z_2} \over {s_1 - s_2}}$ and $d = {{sk-z} \over r}$ where $z_1$ and $z_2$ are the truncated hash bitstring, $s_1$ and $s_2$ are the two corresponding signature component, $r$ being the fixed part in both signatures, and $d$ the private key we hunt.

For more, Wikipedia has an article covering ECDSA and its security.


I would try to avoid doing any cryptography using javascript… but that's just my personal opinion.

Anyway, if you really want to walk the Javascript path, you could skip the libraries and take a look at the window.crypto.getRandomValues() function, as long as you can live with the fact that it's an experimental API and not yet supported in all browsers… it should work on current versions of Firefox and Chrome though.

And for Opera, there's Math.Random() which has been implemented as a CSRNG. But you should be aware that Math.Random will only be a CSRNG in Opera (only in Opera, not any other browser!!!), and that the function will only return 53 bits of entropy on each call.

Besides that, I don't know of any further CSRNGs being available in Javascript, or in Javascript libraries.

EDIT

Some stuff that might help you find solutions to your quest:

"Symmetric Cryptography in Javascript - Stanford Crypto Group" mentions (among other things) entropy-collection for crypto-purposes,
and some sites out there (like https://www.grc.com/r&d/js.htm ) practically show entropy-collection for crypto-purposes using somewhat similar solutions as mentioned in the above paper.


What is the advantage of an attacker over breaking a 4 digits PIN?

Something went wrong with you calculations there :) A single digit has $10$ possible values, not $2^{10}$. What you were probably trying to calculate was $\frac{1}{10^4}=\frac{1}{10000}$.

It is a bit unclear what you mean by advantage. In cryptography, the advantage $\mathsf{Adv}_\mathcal{A}$ of an adversary $\mathcal{A}$ is the probability that $\mathcal{A}$ is successful ($\mathsf{Succ}_\mathcal{A}$) in attacking something minus the success probability for some trivial attack that cannot be prevented.

For example, for a decision problem, such as CPA security, the advantage is $\mathsf{Adv}_\mathcal{A}=\mathsf{Succ}_\mathcal{A}-\frac{1}{2}$. This is because you acannot prevent $\mathcal{A}$ from guessing the bit.

The advantage of guessing a four digit PIN with one random guess is $1/10^4$.
For at most $t$ random (but distinct) guesses, we get $\frac{t}{10^4}$.
The advantage for an adversary attacking some authentication service using four digit PINs would therefore usually be $\mathsf{Adv}_\mathcal{A}=\mathsf{Succ}_\mathcal{A}-\frac{t}{10^4}$.

EDIT: In the first version of this answer I assumed that PINs would be chosen uniformly for each try. Of course that's not true. They would indeed be chosen to be distinct from each other. (This makes the probabilities quite a bit easier.)


Prime modulus for RSA and sharing a secret?

I think the confusion lies in mixing two distinct hard problems.

RSA is related to the difficulty of factoring large numbers. The scheme you link to in the paper is based on the difficulty of solving discrete logarithms. Since they are very different hard problems, you can't really compare the two in terms of what must be kept secret.

For RSA, $\varphi(n)$ must be kept secret since with that you could factor $n$ (and hence make the hard problem easy). With the scheme you link to, you must keep the exponent secret as that is what you are trying to solve for when computing a discrete logarithm.


SHACAL-2 vs. AES as underlying block cipher for Secure Hash (aka SHA-256)

Using AES as a Davies Meyer compression function is a bad idea:

It has a block size of 128 bits, which limits its collision resistance to 64 bits, which is rather weak.
This limitation could be overcome by using Rijndael with a 256 bit block size, but then you'd need to use a higher number of rounds.

AES has been designed to work with randomly chosen keys, not with attacker chosen keys.
AES suffers from related key attacks. While I'm not aware of published a way to exploit this to find collisions, it certainly undermines my confidence is such a construction. You could increase the number of rounds to compensate for this, but that'd decrease performance.
See Are AES-256's related-key weaknesses exploitable if it is used to build a hash?

Block ciphers designed for use in hash functions have very cheap key setups. While AES isn't as expensive as Blowfish, changing the key still has a noticeable performance impact.

Fewer rounds doesn't necessarily mean more efficient:
Comparing the absolute number of rounds of different cryptographic primitives is meaningless. You can design a primitive to have many cheap and simple rounds or fewer more expensive and more complex rounds, resulting in similar performance.
See Why does SHA-1 have 80 rounds?
AES isn't that fast on a CPU without special instructions, like AES-NI, probably even slower than SHA-2 on some CPUs.


What other one-way functions are used in cryptosystems?

The Merkle–Hellman knapsack cryptosystem was based on a variation of the subset sum problem.  (It was broken by Adi Shamir a few years after it was developed.)

  Given a set of numbers $A$ and a number b, find a subset of $A$, which sums to b.

The cryptosystem relies on the fact that in this form of the subset sum problem if the set $A$ is superincreasing (each element of the set is greater than the sum of all the previous elements), the problem is solvable in polynomial time.  Also, you can transform the superincreasing set $A$ into a non-superincreasing set $B$ using a multiplier $r$ and a modulus $q$.

Solving the subset sum problem with a non-superincreasing set ($B$) is NP-complete, so you can use $B$ as a public key to encrypt messages, then use $A$, $r$, and $q$ as a private key to decrypt them.


How to create a PEM file for storing an RSA key?

RFC 2313 specifies the RSAPrivateKey ASN1 structure as a SEQUENCE containing the INTEGERs

$0$;
$n$;
$e$;
$d$;
$p$;
$q$;
$d\bmod(p-1)$;
$d\bmod(q-1)$;
$q^{-1}\bmod p$.

The PEM format consists of such a structure encoded as Base64 and framed by the typical BEGIN/END RSA PRIVATE KEY header and footer lines.
Thus, you can use any ASN1 library you like to encode the private key parameters. For example, with Python's pyasn1 module, a private key file's contents can be obtained as follows:
import pyasn1.codec.der.encoder
import pyasn1.type.univ
import base64

def pempriv(n, e, d, p, q, dP, dQ, qInv):
    template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for i,x in enumerate((0, n, e, d, p, q, dP, dQ, qInv)):
        seq.setComponentByPosition(i, pyasn1.type.univ.Integer(x))
    der = pyasn1.codec.der.encoder.encode(seq)
    return template.format(base64.encodebytes(der).decode('ascii'))

The parameters dP, dQ and qInv are most easily (as in: lines of code) computed as follows:
dP = d % (p-1)
dQ = d % (q-1)
qInv = pow(q, p-2, p)


HMAC-SHA-256 vs SHA-512/256 vs truncated SHA-512 for use as a MAC

Option 2 and 3 are appropriate for a MAC, assuming the length of the key is not variable (otherwise appropriate padding must be used, similar to that used in KMAC). In this manner, it behaves like SHA-3 which does not need to be run in the usual nested HMAC construction. Numbers 2 and 3 are actually virtually identical. The only difference is that SHA-512/256 uses a different IV than plain truncated SHA-512. They all provide protection against length extension attacks.

Note that you can optimize HMAC to reduce the number of calls to the hash. Any decent implementation will not have significantly impaired performance compared to HMAC-SHA-256. You can also get away with only executing a single SHA-256 function using an older construction called an envelope MAC which concatenates the key, message, and key again, with padding.


P2P encryption - Do I need a different session key each time?

No, having a different session key each time is not strictly necessary. The generic justification is that all modern ciphers and Message Authentication Codes, including AES128-CBC and HMAC, are specified to allow a key to be safely reused for multiple messages.

Note: the One Time Pad does not allow reuse of its pad/key for multiple messages, but is not an exception; it just does not match the modern definition of a cipher.

For CBC with a $b$-bit block, and fully random IV, the best generic attack (for chosen plaintext) requires that there is an accidental collision in the ciphertext blocks, and that has demonstrably odds less than $n^2/2^{b+1}$ to occur after $n$ blocks of $b$ bits have been encrypted. For AES, $b=128$, so if one enciphers less than $2^{60}$ octets (including padding) across all the sessions, residual odds of any attack due to CBC are demonstrably less than $2^{-17}$; and then that is only expected to compromise a few blocks of plaintext, or allow to test if the plaintext has some characteristic.

HMAC with any common hash (including the broken MD5) resists even better to multiple uses.

Still, there could be good reasons to change the key regularly, including being secure despite:

an insufficiently random IV for CBC (including, a narrow one, or one generated using a poor RNG, including a good PRNG that is poorly seeded);
leakage of key by some side-channel, including plain compromise of a machine using it;
guess of the MAC for a certain message that the attacker wants to be accepted, by some side channel like the archetypal timing attack allowed by comparison using memcmp;
a padding oracle attack.


Types of Cryptography for a 4-8 bit microcontroller

Public-key encryption on microcontrollers

Erik-oliver Blaß ,  Martina Zitterbart.
"Towards Acceptable Public-Key Encryption in Sensor Networks". 2005.

"dsPIC DSC Asymmetric Key Embedded Encryption Library"
an implementation of RSA, Diffie-Hellman, DSA, SHA-1, MD5.
(Are such 16-bit microcontrollers in your range of interest?)

"Links to Embedded Crypto Implementations"
lists a few implementations of RSA on 8 bit microcontrollers.

"full size" symmetric ciphers on microcontrollers

Many people implement cryptography on a microcontroller very similarly to cryptography on any other CPU -- write a program to do encryption or decryption using the same ciphers we use on any other CPU.
Quite a few modern 8-bit microcontrollers have enough program memory (often called "ROM" for historical reasons, although today it's usually Flash memory) and RAM and processing speed to handle the full Advanced Encryption Standard (AES)(a)(b)(c)(d), Triple Data Encryption Standard (3DES)(a)(b), Enigma(a), RC4(a),
as well as less-known algorithms
such as Alexander Pukall’s PC1 (a).

symmetric ciphers designed for low RAM

Quite a few microcontrollers have 256 bytes of RAM or less. A few full-size ciphers work just fine, but ciphers like RC4 seem impossible to implement in this environment.
A few symmetric ciphers seem specifically designed for this environment -- KeeLoq, TEA, XXTEA, etc.

Other cryptographic techniques for microcontrollers

A few bootloaders for embedded systems use encryption.( "USB PIC Bootloader with XTEA encryption" )

Rather than doing the encryption in the CPU itself, a few systems have an external chip that does crypto stuff.
( CryptoAuthentication, CryptoMemory, Trusted Platform Module, etc. )
Such dedicated circuitry, hard-wired to perform some calculation, often requires significantly less power than a more general-purpose CPU programmed to perform the same calculation.
This way newly-introduced bugs in the software on the main CPU can't possibly leak the secret keys stored in that external chip, or introduce new flaws (new timing attacks, etc.) in the algorithm implemented in that external chip.


Is it possible to unpad a file that is not padded

Yes, it is quite possible that after decryption, a file that was not encrypted falsely appears to be encrypted with correct padding.

For a file of random byte length, there is probability 1/16 (6.25%) that its length is that of a valid encrypted file, and then there is probability just below 1/255 (≈0.392%) that after decryption, the last block ends with 01, or 0202, or 030303, or 04040404...

All in all, nearly one random file (of both random length and content) out of 4080 would wrongly pass the test.


Making brute force attacks less effective through obfuscation?

Since speaking about any software is not showing anything, I'll instead on how they do it and where they do it.

This "obfuscation" is very often done when passwords come into play. There are plenty of good passwords hashing functions, that slow attacker down by "obfuscating" it, then brute-force has to use that same "obfuscation" which is designed to be slow. This is done because users will always generate weak passwords, it isn't something we can fix. But this is still futile attempt at fixing something that is inherently broken (users will always devise poor and short passwords). It is far more effective to make passwords twice as long than making "password check" take twice as long. Increasing key by ONE BIT doubles security. Increasing check time by factor of 2 doubles security.

Apart from passwords, we almost never use such "obfuscations" because they are not effective at stopping attacker. Making key double length will increase security by unimaginable factor, doubling encryption will only double security!

  If I were inventing things instead of asking questions, I would have my software do a block cipher on the plain data and append the key to the newly encrypted data. I'd have it do this at least twice, now the data would look like uniformly distributed random data (because both the key and encrypted message are), and the attacker would have to number crunch at least 1 full decryption of the message for each brute force attempt.

This would not help you. I'd simply take twice as long to decrypt your message. This is not a lot, as computing power increases very fast so at worst I'd wait a year to break your scheme. On the flip side, you would have to take twice as long to encrypt that message. We end up being hit same.

History likes to repeat itself. Germans tried to fix enigma by using more and more complex encoding schemes, it didn't help. RC4 was "fixed" by removing first X bytes, it didn't help in long run (everything before fix was compromised, everything after fix was safe for some years). It's easy to fall into pitfall of "I'll just change it a bit and it will be secure again", truth is we don't know how long it will be secure, so it's best to leave whatever is broken behind, making better, more effective algorithms.

  but they still design systems to be strong against brute force attacks, that is why people keep making keys longer.

Problem is, you are not even making key longer. Key only makes sense if increasing key by X will increase security by larger margin than X. You instead make it so that it takes two times longer for you and attacker. It doesn't make difference in long run for attacker. RSA is special case, because RSA inherently has better factoring algorithms than bruteforce, and we move away from RSA now because it's not efficient enough. If RSA got cracked however, making better algorithms, we would probably totally move away from RSA, because we couldn't make key large enough for attacker to be powerless. RSA is also far different from symmetric ciphers, because of efficiency, breakage method etc. so comparing two isn't correct.


NIST temporarily closed — will that have a negative impact on the future of cryptography?

This closure is a rather stupid thing, because the Web site is not closed: indeed, there still is a machine, somewhere, which responds to HTTP requests and returns the "we are closed" page. It would have cost zero effort, and zero extra money, to simply let the Web site run and keep on serving PDF files.

For crypto development, this means that until the US Republicans and Democrats finally agree on who is the Alpha Male, developers will need to find the relevant standards and test vectors elsewhere. A lot of the information is duplicated elsewhere; e.g. FIPS 180-4, which defines the SHA-* functions, has also been copied as RFC 6234, which is still available. Also, many people already have copies of the documents they are working on (I know that my "Downloads" directory must have a lot of NIST pdf files in it).

In any case, crypto development, by necessity, works at the pace of research, with a lot of thinking. Thinking has not stopped. Publication of documents, writing of standards, organization of meetings... operates on a time scale counted in weeks or months, not days. A few days of bureaucratic-induced closure is not enough to show up on the big picture of cryptographic advances.


RSA factorization knowing N, e=65537 and g=d*(p-17)

Fermat's little theorem is useful indeed.

For instance, for almost any integer $m$, you have that $m^{P-1}=1 \mod{P}$.
Since then, you know that $A=m^{P-1}-1$ is a multiple of $P$. With that value, you can therefore compute $gcd(A,N)$ which should provide $P$ (knowing that $N=P \times Q$).

With the provided values, you may be able to build that special $A$. For instance, $(m^e)^g \mod{N}=m^{e \times g} \mod{N} = m^{P-17} \mod{N}$.

So $(m^e)^g \times m^{16} = m^{P-1} \mod{N}$ ! To conclude, you can finally compute the gcd between $N$ and $(m^e)^g \times m^{16}-1$.

As an example with small integers, let us define $P=11$, $Q=17$, $N=P \times Q = 187$, $\Phi(N)=(P-1) \times (Q-1) = 10 \times 16 = 160$, $e=3$, $d=107$, $g=d \times (P-17) = 158$ and $m=2$.

One gets $(m^e)^g \mod{N} = 38$ and thus $(m^e)^g \times m^{16} = 89$.
One finds $P$ by computing $gcd(89-1,187)=11=P$ ;-)


Is there any “easy” way to solve the discrete log problem when $p$ is composite?

If you know the factorization of $p = rs$, then it can be reduced to solving the problem $y = g^x \pmod r$ and $y = g^x \pmod s$, and then combining the two solutions; hence you're reduced the hardness of the problem to the harder of the $r, s$ subproblems.

If you don't know the factorization of $p$, then it is at least as difficult as factoring $p$ (if you can solve arbitrary discrete logs modulo $p$, then you can factor $p$).

That would imply that the person who generated $p$ might be able to give himself a backdoor (as he'd have an easier time solving discrete logs than anyone else).

On the other hand, that's not the complete story.

You specified DSA; DSA places more requirements on the group it runs in.  For one, it actually operates in a prime-sized subgroup that is both considerably smaller than the modulus size, and which must be listed in the global parameters (as the verifier needs it).  And, in case you're wondering, the fact that the subgroup is prime is important, if it were composite, you could factor it, and attack each of the factors independently.

So, suppose we had $p = rs$ (where the factorization is secret), and we have a generator $g$ with $g^q = 1 \pmod p$ (for some moderate sized prime $q$).

That immediately implies that we have $g^q = 1 \pmod r$ and $g^q = 1 \pmod s$; however, if we have $g = 1 \pmod r$, then a simple computation of $\operatorname{gcd}(g-1, p)$ would reveal the factorization, and hence to be secure, we must have $g \ne 1 \pmod r$ and $g \ne 1 \pmod s$.

This implies that $r - 1 = 0 \pmod q$ and $s - 1 = 0\pmod q$, or in other words, we have:

$$p = (aq +1)(bq+1)$$

where $q$ is public, and $a, b$ are some unknown integers.

If we go through the size of $q$ (perhaps 256 bits), and the sizes of $r = aq+1$, $s = bq+1$ (perhaps 1024 bits each, hence $a, b$ may be 768 bits each), it's not immediately clear whether current lattice based factorization methods would work, but it's closer than anyone would trust.


How to enforce data privacy, integrity and authenticity of distributed firmware images for an embedded device?

First, if you mean to sign something, you should use a signature algorithm, rather than "RSA encryption" with private key, which on its own may be very weak.

Now the main issue here is that the RSA part is only authenticating the nonce. Anyone who knows the AES key can just encrypt an arbitrary firmware image with a nonce they've already seen. This allows them to reuse the earlier signature. So there's no guarantee of authenticity if the AES key is compromised.

To fix this you could sign the whole encrypted image – nonce, authentication tag and all. With a strong signature algorithm (e.g. RSASSA-PSS) using a strong hash function, there is no way even knowing the AES key to encrypt another image with the same signature.


What is the definition of Feistel Cipher?

According to Definition 7.81 given by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography,

  A Feistel cipher is an iterated cipher mapping a $2t$-bit plaintext $(L_0,R_0)$, for $t$-bit blocks $L_0$ and $R_0$, to a ciphertext $(R_r,L_r)$, through an $r$-round process where $r\ge1$.
  For $1\le i\le r$, round $i$ maps $(L_{i−1},R_{i−1})\xrightarrow{K_i} (L_i,R_i)$ as follows: $L_i=R_{i−1}$, $R_i=L_{i−1}\oplus f(R_{i−1},K_i)$, where each subkey $K_i$ is derived from the cipher key $K$.
  Typically in a Feistel cipher, $r\ge3$ and often is even. The Feistel structure specifically orders the ciphertext output as $(R_r,L_r)$ rather than $(L_r,R_r)$; the blocks are exchanged from their usual order after the last round. Decryption is thereby achieved using the same $r$-round process but with subkeys used in reverse order (...)

On the next page they state, with the contradiction pointed in the question's Q1:

  DES is a Feistel cipher (...)
  An initial bit permutation (IP) precedes the first round; following the last round, the left and right halves are exchanged and, finally, the resulting string is bit-permuted by the inverse of IP.

In Q1: DES is a Feistel cipher, except for IP and IP-1; that deviation keeps the notable property of a pure Feistel cipher that only the order of subkeys differs for encryption and decryption.

In Q2: the construction is a Feistel cipher, except for the above deviation, and an additional final XOR with $K_2$ on encryption, and correspondingly an additional initial XOR with $K_2$ on decryption; this looses the aforementioned notable property of a pure Feistel cipher, and adds a key-dependent transformation.

I would say the answer to Q1 is yes for Jim Kirk, and no for Mr. Spock; while they could agree on no for Q2. The Captain is on option 3 in the question (perhaps also requiring that any key-dependent transformation is thru the Feistel structure); while the logician sticks to 2 (and wants any deviation to be explicit). Nobody on the deck stands for 1.


Your scheme doesn't appear to provide any authentication whatsoever.

For a normal RSA digital signature the intended recipient can calculate the hash of the message, decrypt the signature using the public key to get the original hash, and compare them to authenticate the message. If an attacker is to tamper with the message, then in order to change the signature so that it matches the tampered message they would require access to the private key (which we assume they do not have).

In your scheme, an attacker can simply modify the message and update the "signature" by recalculating the hash of [tampered message + seed]. The attacker must have access to the (unencrypted) seed because it was encrypted with the private key, and so can be decrypted with the public key which we assume the attacker has. If the seed was instead encrypted with the public key, then the attacker would not be able to decrypt it to get the original seed in order to calculate a new hash, but nobody else would be able to either so it would be impossible for the intended recipient to verify the signature is correct.


Digital Signature using symmetric key cryptography

You may be interested in reading up on the The TESLA Broadcast Authentication Protocol which uses the one-way key chain concept to achieve authentication.

The basic idea of the key chain is to hash a secret key value repeatedly and use the hashes or "keys" in the reverse order for authentication. A simple example would be for Alice to compute

         H(H(H(H(secret key))))

and send this value securely to the Bob. Next, Alice disclose the value of

         H(H(H(secret key))).

Since the hash function, H(.) is assumed to be one-way then any party with knowledge of the pre-image is assumed to be Alice.

The sender uses the most recent value from the one-way chain as a cryptographic key to compute a MAC. Each receiver can verify that the disclosed key is correct (using self-authentication and previously released keys). The authors state that any key of the key chain can serve as a key chain commitment and is similar to a public key of a digital signature


Merkle–Damgård padded block concatenated outside the compression function hash?

Why don't you look at it the other way; suppose you could find a collision with your modified H(x) = h(ZB - 1 || XB) || L; could you use that collision to find a collision in the original H?


Fix $k$, $r$, and $m$.  Consider $t = F(k, r) \oplus \operatorname{CRC32}(m)$.  Can you relate it to $t' = F(k, r) \oplus \operatorname{CRC32}(m \oplus \delta)$?


Known Plaintext Attack for Modified OFB Mode of Operation

It should be $256*128 = 4096$ bytes. The period at most 256 and each encryption outputs 128-bits.
When the $FB,FB,\ldots,FB$ series enter the plaintext, again we are taking the 8 MSB form the ciphertext that has still 256 different possibilities. To see the picture clearly;

In the first case the input space has only 256 plaintexts consist of 120-zero and the 8-bit.
In the second case the input space still has 256 plaintexts consist of repeating bytes. $$00\ldots 00, 01\ldots 01, \ldots , FF\ldots FF$$ Again, once $$FB_i = FB_j, i \neq j$$ we will have a cycle with at most 256 period.


Encrypt large data with RSA through blocks in java

The system is probably meant to effectively use an "RSA signature" on top of RSA encryption. If you used raw RSA it could "work", but only if the client's modulus is larger than the server's – or you get lucky and the encrypted key is small enough. Since you are using a library that handles padding for you, it expects a small enough input that it can pad it to size for encryption.

If you can, you could instead use an actual RSA signature algorithm in the second step. This would let the server to verify who the encrypted key is from.

However, if the protocol is something you must use, you should double check that you have understood it correctly. As you have stated it, it seems broken.


Given p and q of DSA how do you show they are prime?

I am given $p = 4916335901$, $q = 88903$ and am asked to show these are prime

To check whether a given integer $n$ is prime you have to check whether it is only divisible by $1$ and $n$, i.e., that it is not a composite integer. If you are given such an integer you can either factor the given integer, use primality tests to check for primality or in case of such small numbers just ask Wolfram alpha. In your case, both $p$ and $q$ are indeed prime, and your given $p$ is of the form $p=k\cdot q +1$. Most often one encounters the use of $k=2$, so called safe primes in cryptography. You can generate such primes even in the size for cryptographic purposes efficiently.

  as well as $q|(p-1)$ in DSA.

The notation $a|b$ means that $a$ evenly divides $b$, i.e., $b$ divided by $a$ gives a remainder of zero. This is easy to check by computing $\frac{4916335901-1}{88903}=55300$, so yes $q|(p-1)$.

Using a prime of the form $p=k\cdot q+1$ with small $k$, you know that when you are working in ${\mathbb Z}_p^*$ (which has order $p-1$) that you have a cyclic subgroup of prime order $q$.


This sounds exactly like secret-sharing. Briefly, you can secret share a secret key $sk$ in a k-out-of n fashion where the corresponding public key $pk$ is known by everyone.

Then, everyone can encrypt a message $m$ to a ciphertext $c$ using the public key yet, only a quorum of size $k$ can decrypt $c$.

In particular, this kind of secret sharing can be done without any central party by running a distributed key generation algorithm (DKG) among participants.


Existential Unforgeability of signature scheme against Adaptive Chosen Message Attack

These are standard terms in the cryptographic literature. Refer to Goldwasser's Lecture Notes on Cryptography, particularly section 10.3.1 where the definitions of forgery of digital signatures are introduced:

Existential Forgery: The adversary succeeds in forging the signature of one message, not necessarily of his choice.
Selective Forgery: The adversary succeeds in forging the signature of some message of his choice.
Universal Forgery: The adversary, although unable to find the secret key of the The forger, is able to forge the signature of any message.
Total Break: The adversary can compute the signer’s secret key.

The exact use of these definitions can be seen later in the notes in which some proofs are discussed.


Removing "security by obscurity" from port knocking

The essence of port knocking - namely, the concealment of a service behind a lightweight authenticator - does not categorically suffer from security through obscurity. It really depends on what the characteristics of the authenticator are. At one end of the spectrum, there is "open port 22 if a SYN packet is sent first to port 12345" (obscurity - even nmap becomes a legitimate port knocking client in this case), and at the other end of the spectrum is PK's big brother "Single Packet Authorization" (which can use 2048-bit GnuPG keys together with an HMAC for example). The fwknop SPA implementation can do the later: https://www.cipherdyne.org/fwknop/
(Disclaimer: I wrote fwknop, so I'm obviously biased, but I believe the point still stands.) You may find additional material in the fwknop tutorial useful: http://www.cipherdyne.org/fwknop/docs/fwknop-tutorial.html

Also, the best reference on Port Knocking and SPA is still Sebastien Jeanquier's thesis "An Analysis of Port Knocking and Single Packet Authorization": http://www.securitygeneration.com/wp-content/uploads/2010/05/An-Analysis-of-Port-Knocking-and-Single-Packet-Authorization-Sebastien-Jeanquier.pdf


Weakening of Paillier cryptosystem due to ciphertext equivalence and order in CryptDB

Your hunch is wrong because of the definition of CPA security: Assume that some knowing some kind of relation between two plaintexts would give the attacker an advantage.

Now think of the INC-CPA game: Nothing stops the attacker from choosing exactly this kind of relationship. And if the scheme is IND-CPA secure, knowledge of such a relation does not break the scheme. As mikeazo pointed out: Even if you only use a message space of $\{0,1\}$, CPA security still ensures the attacker can not distinguish their encryptions.

The other aspect you hinted at: Under CPA security it is not possible to distinguish whether two ciphertexts encrypt the same plaintext: The attacker can encrypt $m_1$ and $m_2$ as often as he wishes. If there was a way to determine that one of the encryptions encrypts the same ciphertext as the challenge, he wins.


Difference with round keys and round constant in AES

Round keys are not the same as round constants. A round constant is always the same no matter what the key is. The round keys, however, are an expanded representation of the AES key being used.

For more information, read up on the AES key schedule.


Consult the transcript from the class, there is an example he works through which is very similar to this problem. Fundamentally you're trying to solve the problem c = (T + T(-N^-1) (mod R)N)/R (mod N). I suggest creating an equation in Excel (or other tool of your choice). Test your equation using the inputs from the example problem (EXAMPLE INPUTS: T=69, N=109, R=128, -N^-1 = 27). When you're confident your equation is working for that (EXAMPLE PROBLEM SOLUTION = 61), then plug in the values for this problem. Hint: T = 25 for this problem.


Almost (epsilon) perfect secrecy - lower bound of keyspace size

Short answer: the two definitions are not equivalent.
Long answer:

The condition $|\Pr[M=m\mid C=c]-\Pr[M=m]|\leq\epsilon$ doesn't allow us to have less keys than messages. Encrypt an arbitrary message to get a ciphertext $c$, then use all keys to decrypt $c$. If $|K| \lt |M|$, there exists a message $m$ which can not be decrypted from $c$ using any key.
Then $|\Pr[M=m\mid C=c]-\Pr[M=m]| = \Pr[M=m]$ and since we can assign an arbitrary distribution to our message space, we can make $\Pr[M=m] > \epsilon$

The definition of $\epsilon$-perfect secrecy given in the book (the one you show in the image) does allow us to have fewer keys than messages. For example:
Suppose the message space $M$ contains all 4 English letter words, $|M|$ = $26^4$. Let's use a one-time-pad encryption scheme without the identity key, thus $|K|$ = $|M| - 1$.
Any adversary playing a game will choose two messages $m_0$, $m_1$. If our returned ciphertext $c=m_0$ the adversary knows for sure that the encrypted message is $m_1$. If our returned ciphertext $c=m_1$ the adversary knows for sure that the encrypted message is $m_0$. But if we return any other ciphertext, the one-time-pad scheme ensures that the best an adversary can do is to make a random guess. Therefore, the probability for an adversary to win a game is not greater than
$1 \cdot \Pr(c \in \{m_0, m_1\}) + \frac{1}{2} \cdot (1 - \Pr(c \in \{m_0, m_1\}))$ = $\frac{1}{2} + \Pr(c \in \{m_0, m_1\}) \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2|K|}$
Thus, this scheme achieves $\epsilon$ perfect secrecy if $\epsilon \geq \frac{1}{2|M-1|}$

Let's find a lower bound for $\epsilon$. Suppose an adversary chooses $m_0$ and $m_1$ uniformly at random. Upon receiving a ciphertext $c$ it computes $M_c = \{ m | \exists k. enc_k(m) = c\}$ (it might be computationally infeasible to compute $M_c$, but we're not concerned about computational resources in this exercise).
Note that at least one of $m_0, m_1$ is in $M_c$. If some $m_i \not \in M_c$ the adversary knows for sure that the encrypted message is the other one. If both messages are in $M_c$, the adversary makes a random guess.
The probability of such adversary succeeding is
$\frac{1}{2} \cdot \Pr(m_0, m_1 \in M_c) + 1 \cdot (1-\Pr(m_0, m_1 \in M_c))$ = $ 1 - \Pr(m_o, m_1 \in M_c) \cdot \frac{1}{2}$
Let's estimate $\Pr(m_0, m_1 \in M_c)$ - the probability that both messages are in $M_c$. One message will certainly be in $M_c$ because we encrypted it to $c$, the other message is chosen uniformly at random from $M$, so the probability of both being in $M_c$ is $|M_c| / |M| \leq |K| / |M|$
Thus an adversary can win a game with a probability $p \geq 1 - |K| / |M| \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2} \cdot (|M| - |K|) / |M|$. If we want $\epsilon$ secrecy we must have $\frac{1}{2} + \epsilon \geq p$ which implies that:
$|K| \geq |M| \cdot (1-2\epsilon)$
note that I have not shown this lower bound is attainable.


You could try the 112-bit secp112r1 cited in [1].

Before you do this, the problem with that paper is they actually show how to break the discrete log problem on this curve! And this was back in 2012. So any export-strength implementation of ECC is definitely breakable by governments, research groups and sufficiently determined/resourceful commercial adversaries.

So you'd be selling crypto that, while safely exportable, is known to be breakable and you're competing against other crypto libraries that don't have this "feature". I'm skeptical whether this is a sensible idea.

EDIT: oops, I forgot to check the key point - that it's patent-free. But the problem remains that any 112-bit curve, patented or not, is small enough that one can feasibly if not easily take discrete logs.

EDIT2: on my machine, openssl ecparam -list_curves includes secp112r1 and according to [2] sun wrote the OpenSSL ECC package "precisely to avoid any patented method". To me it looks like you should be fine with that curve as long as you don't re-implement it using any of the patented implementation techniques. This is not legal advice of course.

[1] http://lacal.epfl.ch/files/content/sites/lacal/files/papers/noan112.pdf

[2] https://security.stackexchange.com/questions/3519/can-ecc-be-used-without-infringing-on-patents


The goal, the method, and the interface of the signcrypt primitive.

1. Order of signing and encrypting.

It is often done in authenticated encryption to Encrypt-Then-MAC. However, there's a bit of problem with Encrypt-Then-Sign here as mentioned by the linked answer in the linked question. So it's better to sign-then-encrypt unless we have a more dedicated signcrypt algorithm.

 2. The Interface.

The tuple generally consist of the following functions:

$\operatorname{GenSign}(\langle \text{entropy source}\rangle) \to (\text{key}_\text{sign}, \text{key}_\text{verify})$

$\operatorname{GenEnc}(\langle \text{entropy source}\rangle) \to (\text{key}_\text{enc}, \text{key}_\text{dec})$

$\operatorname{SignEnc}(\text{msg}, \text{key}_\text{sign}, \text{key}_\text{enc}) \to \text{ciphertext}$

$\operatorname{VerifyDec}(\text{ciphertext}, \text{key}_\text{verify}, \text{key}_\text{dec}) \to \text{msg}$ or $\text{FAIL}$

 3. Instant Messaging Protocol.

The double ratchet "instant messaging" protocol had already solved the confidentiality problem from two ends: forward secrecy and future secrecy. So it's only needed to sign the message in such framework.


Proper encryption algorithm to use when encrypting data before backing it up to untrusted hosts?

Why not gpg? The libraries are already written and open sourced, so you don't have to recreate the wheel.

Split the file into blocks, then add a control file adding whatever metadata you need to keep the files together and belonging to the correct person. Encrypt each block with the user's key, and put it on an untrusted host. He will then be the only person who can decrypt the files. Assuming the untrusted host doesn't delete the blocks.