Does order matter for RSA when used multiple times?

In textbook RSA, one can apply the public key function $x\to E(x) =x^e\bmod n$ and the private key function $x\to D(x)=x^d\bmod n$ in any arbitrary order multiple times and come back to the starting number, as long as one use both keys the same number of times, and the starting number was in the set $\{0,1,\dots,n-1\}$ (also known as $\mathbb Z_n$ ).

Proof follows from the fact that, assuming proper choice of RSA parameters, $E$ and $D$ are inverse permutations of some set. Using that sole fact, we can prove that applying $i$ times $D$ and $j$ times $E$ to any elements of the set, in any order, is equivalent to applying $i-j$ times $D$ if $i-j$ is positive, or $j-i$ times $E$ otherwise. Proof is by induction on $i+j$.

Fact 3 in the question (which is true for any permutation on a finite set) was not used.

As rightly pointed in comment: RSA as actually used for encryption and decryption adds extra operations like padding to textbook RSA, and that destroys the property discussed; in particular, because the encrypted message's space is larger than the message's space.


RSA: Decrypting message with public key and private key

Your ciphertext is A3 BB 05 00

In RSA, the ciphertext is always larger than the original data. In this case, the keys are 32 bits, which is 4 bytes, and A3 BB 05 00 is four bytes


So is it mean that for all AES transformations IV should have only one
  size (128-bit)?

No, not really. The acceptable size for the IV is defined by the mode of operation. Some modes require a full block size as the IV (CBC, CTR, ...), others a bit less and again others take just about any length of an IV that you throw at them (GCM, ...).

  What the sense of this transformation if it cannot be applied to all
  data?

CBC works by chaining full blocks together. Thus you need to process a multiple of the block size. Normally if we don't have a multiple of the block size we pad our data to this size, but in this case you chose to disable padding and as such the length restriction applies.

  For which modes IV is necessary/optional?

Any mode that does not take an IV is trivially insecure under standard security definitions. As such it is strongly recommended against using any such mode (like ECB or SIV) unless absolutely neccessary. Every other mode requires an IV. And if you need an IV for encryption you'll also need one for decryption and vice versa.


Is lattice-based cryptography relevant in symmetric cryptography?

No, it is not, assuming you are talking about symmetric ciphers, pseudorandom generators, and hash algorithms.* Symmetric cryptography does not need to use any mathematical hardness problem to be secure, and there is no need to have a security reduction to one. It is technically possible to design a symmetric algorithm out of a core construct that is normally used for asymmetric cryptography, as in the very slow Blum Blum Shub or the backdoored Dual_EC_DRBG pseudorandom generators, but that's rare. Such constructions have no real advantages over typical symmetric ones.

Note that you do not need dedicated post-quantum cryptography to protect your symmetric encryption keys. The quantum Grover's algorithm does not hit symmetric cryptography nearly as hard as Shor's algorithm hits asymmetric cryptography. Even with extremely high-speed and low-latency quantum computers, it would suffice to double your key length from 128 to 256 to remain safe.

* If you consider homomorphic encryption to be symmetric, then the answer might very well be yes.


The opcode 15 49 (0F 31 - Intel opcodes are more typically listed in hexidecimal) is the RDTSC instruction; this loads the number of cycles since the last rest into EDX:EAX.

By running this function, running some code, and then running this function again, and subtracting the results, you get precisely how long the code takes (in number of CPU cycles).


How to efficiently generate a stream of independent, but biased random bits?

If you want an answer that is maximally efficient in consuming a stream of random bits, then you need a decoder for arithmetic encoding.  However if you're using a moderately fast CSPRNG, why would you sacrifice extra clock cycles to squeeze all the biased bits you can from each unbiased bit?


Should the nonce passed to GCM be authenticated?

Should the external nonce passed to GCM be authenticated separately when passing over network?

No, that is not necessary; it is implicitly authenticated by GCM itself, pretty much as the AAD is also authenticated.  That is, if someone in the middle modifies the nonce, then that will alter the authentication tag that the decryptor computes as a part of the GCM decryption process (and alters it in a way that cannot be predicted by someone without the key).  Because the tag will not match the authentication tag that comes with the encrypted packet, the altered packet will be rejected.


Security Implications of Fixed & Opposite Fixed Points of Sbox


Why is elliptic curve parameter $a=-3$ somehow special

The reason is that choosing $a=-3$ allows for a more efficient computation of the doubling operation, when used in projective coordinates.

In fact if you look at the doubling formula in, for example, Jacobian coordinates from wikibooks you can see that it requires the computation of an intermediate value as $M = 3*X^2 + a*Z^4$, where $(X,Y,Z)$ is the Jacobian representation of the affine point $(x,y)$ through the relation $(x,y) = (X/Z^2,Y/Z^3)$.

That formula to compute $M$ can be simplified to $M = 3*(X + Z^2)*(X - Z^2)$ exchanging the computation of two squares $X^2$ and $(Z^2)^2$ with the multiplication $(X + Z^2)*(X - Z^2)$ and, of course, you also avoided the multiplication by $a$.

This results in a more efficient computation of the doubling formula and works well even in homegeneous or Chudnovsky coordinates.


When working with modulo arithmetic, in case of trouble, get back at what the notation used truly leans. When the question correctly derives $18\,a+0=12$, that really is a shorthand for $18\,a+0\equiv12\pmod{26}$. By definition of the equivalence..modulo notation, that is meaning $(18\,a+0)-12$ is divisible by $26$ when computing in (signed) integers $\mathbb Z$. An integer is divisible by $26$ if and only if it is divisible by $2$ and $13$. The rest will follow.

More generally, when an equation holds modulo a squarefree integer, that equation is equivalent to the combination of equations obtained by replacing the modulo by each of its prime factors. So here we get
$$18\,a\equiv12\pmod2\;\;\;\text{ and }\;\;\;\;18\,a\equiv12\pmod{13}$$
or, reducing,
$$0\,a\equiv0\pmod2\;\;\;\text{ and }\;\;\;\;5\,a\equiv12\pmod{13}$$
The first is a tautology, and the second can be solved by multiplying by the inverse of $5$ modulo $13$, that is $8$, giving $a\equiv5\pmod{13}$.

That gives two possible $a$ modulo $26$: $a$ can be $5$ or $18$. The second is obtained by adding the modulus $13$ to $5$. More generally, given $a$ modulo $u$ with $0\le a<u$, there are $v$ values for $a$ modulo the product $u\;v$ with $0\le a<u\;v$ , and these are $a+k\;v$ with $0\le k<v$.

The value of $b$ corresponding to a given $a$ is obtained by moving that value of $a$ in either of the two equations $6\,a+b\equiv19\pmod{26}$ or $14\,a+b\equiv7\pmod{26}$, and pulling $b$. Both values of $a$ yield that $b$ is $15$ (modulo $26$). That's no coincidence.

Therefore, beyond $(a,b)=(5,15)$, there is an alternate solution $(a,b)=(18,15)$. More plaintext is required to recover the full key.


What is the starting point of Hellman's TMTO method?

Given the diagram, yes they are randomly selected keys, $P$ is a fixed plaintext and the projection of the output to the keyspace gives you the next input as key to the cipher, thus creating a pseudorandom walk through the keyspace.


blowfish ecb with openssl doesn't give the expected result

The -bf-ecb cipher is expanding the key to 128 bits by zero extending it.

The output from -p is the telltale here:

$ openssl enc -bf-ecb -e -in plaintext.txt -out ciphertext.txt -nosalt -K FFFFFFFFFFFFFFFF -p
key=FFFFFFFFFFFFFFFF0000000000000000

Blowfish is defined for 32-448 bit keys, and it appears the OpenSSL implementation chose 128 bits as the size to use, and added zero-extension of shorter keys as a 'convenience'.

Compare this with -des-ecb, where DES is only defined for 64 bit keys:

$ openssl enc -des-ecb -e -in plaintext.txt -out ciphertext-des.txt -nosalt -K FFFFFFFFFFFFFFFF -p
key=FFFFFFFFFFFFFFFF


Elliptic Curve Cryptography Encryption and text representation implementation

I don't know your exact scenario. However you have two options to encrypt data using elliptic curve cryptography (ECC). I'd recommend going with the first option I present.

Use elliptic curve integrated encryption scheme (ECIES). ECIES basically performs ElGamal-like encryption on a key. The key is generated at random and encrypted like in ElGamal (replace the multiply operations with add operations). One then can use this symmetric key to symmetricly encrypt and authenticate the data. ECIES defines how to exactly do that. You then go ahead and simply process the data as you normally would using a symmetric encryption scheme.
Use generalized ElGamal on elliptic curves (no abbreviation, likely never deployed or proposed outside of ECIES). You can as well simply use the generalized ElGamal construction and somehow represent the data you want to encrypt as a point on your curve (which is harder than it sounds).I do not recommend this method. The reason is that you're limited to a message space of 256 to 512 bit (32-64 bytes) and that representing your message may actually be quite difficult, as the reconstruction of the message data from the "decrypted" point won't be easy.

If you're question was only aiming at "How can I represent my bytes in the textfile for the encryption?", then by using approach no. 1 the solution is rather straightforward and with approach no. 2 you have to invent some scheme yourself to aid re-construction. This could go as follows:

Represent your message as octet string $B$.
Convert the octet string to an integer $b$.
Initialize $c=0$
Check if $b$ is a valid x-coordinate on your curve, if yes go to step 6
Set $b=b+1$ and $c=c+1$ and go to step 4
Encrypt the data and append $c$ (maybe with some sort of separator)

Reconstruction should be more easy. You retrieve $b$ by decrypting the message and setting $b$ to be the x-coordinate of the resulting point. Now you simply subract $c$ from $b$ yielding the original $b$ value and making you able to reconvert the integer to a byte array (the text in your file).

Note: If an attacker tampers with $c$, he can let you decrypt the ciphertext to arbitrary messages. Because of this property you should always prefer ECIES.


Should Ed25519 signature verification check the order and canonicity of its inputs?

Public key: Generally, no.  If a legitimate signer is trying to pull a fast one on you, they already have the power to sign messages that you will accept.  So why would they bother feeding you a point that is not generated by the standard base point, when they could just feed you bogus signed messages?

Signature: Generally, no.  The verification equation for a signature $(R, s)$ under public key $A$ on a message $m$, where $A$ is a curve point, $R$ is a curve point, $s$ is a scalar, and $m$ is a bit string, is $$[8 s] B = [8] R + [8 H(R, A, m)] A.$$  If $A$ is an 8-torsion point, then the legitimate signer is already pulling a fast one on you—$(\mathcal O, \ell)$ is a valid signature on any message $m$.  If two points $R$ and $R'$ differ by an 8-torsion point, i.e. if $[8](R - R') = \mathcal O$, then they will both make valid signatures—meaning if a forger could forge one they could forge the other.  But a forger who doesn't know one signature to begin with still can't find one in the first place.

I add the ‘generally’ qualifier because maybe you rely on some properties that signature schemes are not generally expected to provide, such as uniqueness of signatures—as noted, it is easy given a signature $(R, s)$ under $A$ on a message $m$ to find another signature $(R', s') \ne (R, s)$ under $A$ on $m$: pick $s' = s$ and $R' = R + Q$, where $Q$ is any 8-torsion point other than the identity $\mathcal O$.  The assumption of signature uniqueness caused Monero some trouble last year, but most applications do not rely on this.


The Jefferson Disk Cipher is an implementation of this. Each disk is a pre-scrambled alphabet, and the key is the wheel order.


What primitives are needed to generically implement public-key cryptography?

Unfortunately there is no real answer to this. We know that one-way trapdoor permutations suffice, but this is really just an abstraction of factoring. ECDSA/ECIES/ElGamal don't work via any trapdoor permutation, and neither do lattice-based public-key encryption schemes.

In the private-key world, we know that one-way functions are necessary and sufficient. However, we have no analogous primitive that is both necessary and sufficient for public-key encryption, beyond itself. (That is, of course, public key encryption is both sufficient and necessary for public-key encryption, but this is a very annoying answer that means nothing.)

Note, that one-way functions are sufficient for building digital signatures, and so the question of what is necessary is really only for public-key encryption.


Using beginning of TLS ecnrypted data to reveal secret

This question boils down to, "Are there known-plaintext attacks against AES-256-CBC?" The answer is: No, no such attacks better than brute force are known. This would constitute a catastrophic break in AES-256-CBC, and any cipher broken in such a way would be abandoned rapidly.


How to prove correct decryption in Paillier cryptosystem

This can be done by using a zero-knowledge proof to prove that a Paillier ciphertext is an encryption of zero. Specifically, let $c$ be the original ciphertext, and let $m$ be the decryption that Alice sends back to Bob. Then, both Alice and Bob can each locally use the homomorphic property to compute a ciphertext $c'$ that is an encryption of the value encrypted in $c$ minus $m$. Note that if $c$ is an encryption of $m$, then $c'$ is an encryption of zero.

Thus, all that is needed is for Alice to prove in zero-knowledge that $c'$ is an encryption of zero (equivalently, that $c'$ is a $n^2$'d power). This can be done very efficiently, using the method described in Section 5.2 of A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting by Damgard and Jurik.

In light of a comment in a different answer, it is possible for the prover to compute the randomness given the public key, if it doesn't have it. Specifically, let $c=r^N \bmod N^2$ (this is an encryption of zero). Then, compute $M= N^{-1} \bmod \phi(N)$ and $r = c^M \bmod N$. This works since $c^M = r^{N\cdot M} = r^{1+k\cdot \phi(N)}  = r \bmod N$.


Can anyone tell me if there is a glaring problem with my conversion technique?

PrivateECKCDSA = First32Bytes(Hash512(PrivateEdDSA))
PublicECKCDSA = Convert_ED25519_to_Curve25519_public_key(PublicKeyEdDSA)

This conversion makes no sense.

There is no meaningful connection between what you have called PrivateECKCDSA and PublicECKCDSA, so they in no way constitute a key pair.
If by Curve25519 you mean X25519, the public key conversion also doesn't make sense because ECKCDSA needs a full point, not just an $x$ coordinate.
Why are you even doing ECKCDSA over Curve25519?  Are there any protocols that use this?

If you have to use ECKCDSA you most likely have to use a curve standardized by KISA, which is unlikely to have any relation to the curve edwards25519.
If you don't have to use ECKCDSA, why don't you just use Ed25519 signatures?

A note on nomenclature these days: Curve25519 means the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$ over $\mathbb F_{2^{255} - 19}$, while X25519 means the Diffie–Hellman function of $x$-restricted scalar multiplication on Curve25519.  Edwards25519 means the twisted Edwards curve $-u^2 + v^2 = 1 - (121665/121666) u^2 v^2$ over $\mathbb F_{2^{255} - 19}$, while Ed25519 means the EdDSA instance with edwards25519, SHA-512, etc.

  Can any buffer be considered an ECKCDSA private key? I know that because we are using curves and fields there might be some limitation (I'm really clueless about this).

An ECKCDSA private key is a near-uniform random scalar modulo the order of the curve.  For a curve with a 256-bit order, like NIST P-256, you can generally use a uniform random 32-bit string as the private key.

  Also can every EdDSA public key be converted into curve25519, or are some excluded?

Can't meaningfully convert an Ed448 key to an X25519 key.  But if you restrict your question to converting Ed25519 keys to X25519 keys, then the answer is essentially yes: edwards25519 and Curve25519 are birationally equivalent with a map that extends to a group isomorphism, and to almost every Curve25519 public key there are two corresponding Ed25519 public keys.  However, the birational map has a handful of exceptional cases, like $u = 0$, $v = -1$, etc.  So be careful!

  If no named this conversion I'd like to call it the Yaffe Bender key conversion.

Who seeks eponymy, might learn humility!


Is it safe to reuse the salt for generating symmetric keys for a chat application?

You should never re-use a salt, and you should especially not hardcode it for your entire application! A salt has several purposes, including the one you mentioned (defeating rainbow table attacks and others based on precomputation). However, a salt also prevents an attacker from trying to break multiple users' passwords at once. If you use a salt that is not unique, an attacker could trivially build a rainbow table for your application, or attack a batch of users. This is almost as bad as having no salt!

Generally, you want the salt to be exchanged along with the encrypted data or the hash. In this case, you'd want to send the salt and any other unencrypted metadata along with the ciphertext. The salt should be agreed upon by both parties, not generated by the server or any other third party.

With that said, you should not be using an agreed-upon preshared secret password to derive a key for encryption in an end-to-end chat application. The encryption key should be generated using public key encryption. I would recommend using an ECC algorithm like x25519, which is supported by NaCl. The agreed-upon secret should only be used for authentication. That ensures that a weak password does not result in confidentiality loss. You should learn from OTR, which uses SMP for mutual authentication.


Any time there is a choice and password search is an issue, one should prefer scrypt or perhaps bcrypt to stretched-md5, or even PBKDF2.

The reason is that scrypt and bcrypt provide better security, by requiring a bigger investment in hardware (in particular, RAM) for the would-be password cracker, assuming parametrization yielding the same runtime for legitimate use. If enough RAM is available in legitimate use, the additional security obtained by using scrypt can be quite dramatic. See the following table from the paper Stronger Key Derivation via Sequential Memory-Hard Functions defining the Scrypt Password-Based Key Derivation Function.


Are there any examples of signature schemes with multiple signing keys but one verification key?

Maybe you're looking for certificates.  A certificate is a formal signed statement of authority for a user's public key to sign documents.  A certificate is signed by a party called a certification authority whose public key a verifier knows.  A user transmits a message, her certificate, and a signature under the user's private key.  The verifier, knowing only the CA's public key, verifies the certificate with the CA's public key, extracts the enclosed user public key, and verifies the signature with the user public key.  This can be built out of any vanilla signature scheme.

Maybe you're looking for group signatures.  A group of users, and a group manager, gather together to generate keys and publish a public key for the group.  Any member of the group can sign messages on behalf of the group, verified by the group's public key.  The verifier does not ordinarily learn which member signed it, only that someone in the group did, but the group manager can deanonymize signers.  There are a few more security properties; see the article for details and references.  This requires fancy crypto.

Maybe you're looking for multisignatures or collective signatures.  A collective of users gather together to generate keys and publish a public key for the collective.  The collective, or some sufficiently large subset, must all agree to sign any particular message before they can produce a signature that a verifier can verify with the collective's public key.  In an answer to another question yesterday I sketched a simple collective signature scheme out of Ed25519.


Can RFC 5649 be used to wrap multiple keys with the same KEK?

There are basically two purposes for which "ECB mode" encryption (i.e. simply splitting the input plaintext into blocks and applying the raw block cipher encryption function to each block) is safe and useful:

To deterministically encrypt messages up to one cipher block (i.e. 128 bits, for AES) long, in situations where the determinism of the encryption is acceptable (i.e. either it is extremely unlikely for two messages to ever be identical, even under an active attack, or it is acceptable for an adversary to learn if two messages are identical).
As a building block for other encryption schemes with (preferably provably) better security properties.

This is, in fact, what the scheme described in RFC 5649 does.  First, it is a deterministic key wrap scheme: this means that, by design, it does not even attempt to conceal whether or not two wrapped keys are identical.

Second, the scheme described in RFC 5649 only uses AES directly in ECB mode if the key to be wrapped is less than 64 bits long, which means that the key and the 64 bit "IV" together fit in a single 128 bit AES block.  Otherwise, it instead uses the wrapping process described in RFC 3394.  This process is not simple ECB mode encryption, but rather a kind of a wide-block cipher construction built on top of AES.

While RFC 3394 does not contain a security proof for this construction (and if one exists elsewhere, I'm not aware of it), it seems plausible that one could be found, perhaps in a manner similar to Luby and Rackoff's famous 1988 result on Feistel ciphers.  And that's not just my personal guess, either; Rogaway and Shrimpton, who review (and criticize) a version of the scheme in their 2006 paper on deterministic authenticated encryption, also state that:

  "The above criticism notwithstanding, we find it likely that the mechanism is correct. Namely, the modified Feistel network illustrated in Figure 7 is, we conjecture, a secure enciphering scheme (in the sense of a strong, variable-input-length PRP). Scheme AESKW is then seen as an instance of the PTE paradigm, except that the header is folded into the plaintext instead of used to tweak the enciphering scheme."

That said, there's really not much point: in the same paper I just quoted and linked to above, Rogaway and Shrimpton also introduce SIV mode (since then standardized in RFC 5297), which provides a more efficient, flexible and provably secure (in a precise sense also defined in the paper) method for deterministic key wrapping.

As a bonus, in situations where deterministic encryption (and the resulting leak of plaintext equality) is not desired, SIV mode can also be used with an optional nonce to provide a fully CCA secure authenticated encryption scheme.


Standard for asymmetric encryption based on elliptic curves

There is a scheme called the Elliptic Curve Integrated Encryption Scheme that has been "standardized". It is described in section 5.1 of SEC1v2. It is commonly used with EC to create an encryption scheme.

ECIES is a hybrid scheme that depends on a symmetric cipher (and a KDF and MAC algorithm) to encrypt the actual data. Generally that's fine as EC / ElGamal is very limited in what it can encrypt anyway. It is based on ephemeral-static DH, where the ephemeral private key is only used during encryption. You can see it as a delayed key agreement scheme, followed by data encryption.

There are a few problems that makes it trickier than just plain RSA encryption, disregarding the fact that most people find EC cryptography trickier anyway:

some validation of the public key values may be in order if decryption is automated;
the algorithms for the KDF, cipher and MAC are not standardized, so they need to be established in advance;
the ciphertext consists of multiple parts instead of one: the ephemeral public key and the actual ciphertext + MAC value.

The problem that you have to specify the symmetric cipher yourself is why I put "standardized" between quotation marks: you cannot just say that it is ECIES encrypted and expect the other party to be able to decrypt. The configuration parameters for ECIES - and possibly the parameters of the configured algorithms - need to be described.

The benefit is that the ciphertext is generally somewhat smaller and that the decryption operation is more efficient. It is also much easier to have e.g. 256 bit security for the EC keys: just use 512 or 521 bit ECC key pairs (rather than > 16 Kib RSA keys). Besides that, RSA itself is also used in a hybrid scheme since messages are often larger than the modulus minus the required overhead for the padding (PKCS#1 v1.5 or OAEP padding).


Inclusion and Exclusion proofs in RSA accumulators

No and Yes! For the inclusion proof you either need the trapdoor or the accumulated set. However, it is possible to generate exclusion proofs without knowing the trapdoor, i.e. the factorization of the modulus, $N=p\cdot q$, or the size of the group, i.e. $\phi(N)$.
Let $A$ denote the accumulator's current value, $x$ an item, $g$, a generator of the group and $\pi$ the inclusion/exclusion proofs. All arithmetics are done $\mod N$. Also note, that all items (accumulated elements) are primes.
$inclusionProof(A,x): \pi =A^{\frac{1}{x}}$.
Note, that this is only computable if you know the order of the group or the accumulated set as computing $x$th root $\mod N$ is assumed to be hard without knowing the factorization of $N$.
Verifying inclusion proofs is easy, one just need to check whether $\pi^x=A$. Once the item is accumulated, one can easily update her inclusion witnesses.
Let $A=g^u$ be, then,
$exclusionProof(A,x):$ Since $x$ is not accumulated this implies that $gcd(u,x)=1,$ therefore one can compute $a,b$, so-called Bezout-coefficients, such that $ax+bu=gcd(x,u)=1$. Hence $\pi=(g^a,b).$ Verifying the proof is done by checking $(g^a)^x\cdot A^b=g^{ax+ub}=g$.
Batching inclusion/exclusion proofs is also achievable. See this recent result.


They make sense as a starting point, for pseudorandomness.

R1. This is a strict balancedness condition, the difference is 1, in case $N$ is odd and zero is impossible.

R2. If you have an i.i.d. and unbiased binary source, the run length distribution is geometric, which in a finite length segment should follow the profile given in R2, due to the law of large numbers.

R3. Having an autocorrelation $C(t)$ of the form
$$
C(t)=N I\{t=0\}+ f(t) I\{t \neq 0\}
$$
where $I$ is the indicator function, with $f(t)$ small in absolute value is a feature of an i.i.d. independent sequence.
By parseval $|f(t)|\leq 1$ is possible for odd lengths. Golomb chooses this off peak correlation function $f(t)$ as constant so phase information is not leaked.

Of course he also knew that algbraic structures, in particular cyclic difference sets, allowed one to mechanise this two level correlation.


$n = 8369428283 = 81799×102317$ (2 distinct prime factors by Wolfram Alpha)

The $d$ can be found in two ways;

if Euler's totient function $\varphi(n)= (p-1)(q-1) = 8369244168$ is used then

$d = 5788687615 = e^{-1} \bmod 8369244168$

If Carmichael Function $\lambda(n) = \text{LCM}(p-1,q-1) = 4184622084$ is used then

$d=1604065531 = e^{-1}  \bmod 4184622084$

Carmichael Function $\lambda$ provides us the smallest $d$  (lcm versus phi in RSA) and this can be helpful for reducing the timing of decrypting and signing. Here, $d$ calculated with $\lambda(n)$ is two-bit less than $d$ calculated with $\varphi(n)$.

I've encrypted end decrypted both parts by $\varphi(n)$ and $\lambda$ successfully.

[ C =  2 ][ L = 11 ][ A =  0 ][ I =  8 ][ M = 12 ][ Y = 24 ][ O = 14 ]
plaintext       =     CLAIMYO
plaintext int   =   748676046

ciphertext int  =  1773907495
ciphertext char =    AFTHVVNJ
plaintext char  =     CLAIMYO

[ U = 20 ][ R = 17 ][ P = 15 ][ R = 17 ][ I =  8 ][ Z = 25 ][ E =  4 ]
plaintext       =     URPRIZE
plaintext int   =  6387458406

ciphertext int  =  5283907511
ciphertext char =    ARCSTZFZ
plaintext char  =     URPRIZE

note: the A in the ciphertext means 0 as an integer.


Getting the s-box input from its output in differential cryptanalysis on DES

In DES cryptanalysis this is in general achieved by trying all 4 possible preimages for the given S-box output.

In particular, for S-box $S_i$ a 6-bit input (say $b_1b_2 ... b_6$) produces a 4-bit output $a_1a_2a_3a_4$. The s-boxes can then be written as a 2-dimensional array of size 4x16.
The input bits $b_1b_6$ determine the row of the s-box table and the input bits $b_2b_3b_4b_5$ determine the column. The value of the output corresponding to the 6-bit input is the value at cell $S_i[b_1b_6][b_2b_3b_4b_5]$.

Therefore, given an output $a_1a_2a_3a_4$ there are exactly 4 possible inputs corresponding to this output, one in each row of the array corresponding to S-box $S_i.$

If additional information is available - such as Hamming weights within some side channel attacks - this can be done more efficiently.


Advantage of $\operatorname{GF}(2^8)$ over $\mathbb Z/2^8\mathbb Z$ in AES/Rijndael

One important property of the mixColumns step is that it is Maximum Distance Separable (MDS).  That is, if $M$ is our multiplication matrix, if you take any two distinct input vectors $V$ and $V'$, and compute $M \cdot V$ and $M \cdot V'$, the total number of bytes distinct in $V$ and $V'$ plus the total number of bytes distinct in $M \cdot V$ and $M \cdot V'$ will always be at least 5 (the dimension of the matrix $M$ plus 1).

It turns out that this is an important property used in the proof of security of AES against differential and linear cryptanalysis.

Now, if you replace the $GF(2^8)$ multiplications within the MDS matrix with $Z/256$ multiplications, it turns out that you cannot have the MDS property; neither the matrix used within AES, nor any other matrix has the MDS property.

This is fairly easy to show; to start with, consider $V = \{0,0,0,0\}$ and $V'=\{128,0,0,0\}$; these obviously differ in 1 bytes, and so for the MDS property to hold, all for values of $M \cdot V$ and $M \cdot V'$ must differ.  However, if lsbit of $M[0,0]$ is 0, then the first byte of $M \cdot V$ and $M \cdot V'$ will be the same, and hence MDS will not hold, and hence the lsbit of $M[0,0]$ must be a 1.  Along the same line, if we consider the other bytes of $M \cdot V$ and $M \cdot V'$, and additionally, $V'=\{0,128,0,0\}, \{0,0,128,0\}, \{0,0,0,128\}$, we find that all bytes of $M$ must have an lsbit of 1.  Finally, we consider $V'=\{128,128,128,128\}$.  If all the lsbits of $M$ are 1, then $M \cdot V = M \cdot V'$; that is also a violation of the MDS property (as well as making decryption difficult...)


Given some output of unknown seeds after an unknown number of steps, is it "computationally hard" to find a pair of seeds that produce the given output after a number of steps?

Nope; two observations:

With two successive outputs, you can compute the internal state; if you see the outputs $y_1, y_2$, then the internal state immediately after the first output was $x_1 = y_1, x_2 = y_2$

Given the internal state, you can compute previous states; if the state at time $t$ was $x_1 = y_1, x_2 = y_2$, then the state at time $t-1$ was $x_1 = rotl(y_2) \oplus y_1, x_2 = y_1$ (where $rotl$ is 'rotate shift left by one')

These two observations allow an attacker to revert this generator as far as he needs to.
Actually, for reverting arbitrarily long distances, there are other tricks that reduce the number of computations needed (logarithmic in the size of the time delta; constant time is likely possible, but I don't want to promise that), however we don't need to go to that extent to show that this is weak.


How can I prove that ElGamal encryption in $\mathbb{Z}_p^*$ with OAEP padding is ind-CPA secure?

This is not a full answer: I only motivate the use of OAEP on top of ElGamal encryption.

ElGamal encryption as stated in modern literature, that is with message in a group where the Decisional Diffie-Hellman problem is hard, is demonstrably CPA-secure. That does not hold for the original scheme in Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, in proceedings of Crypto 1984, even with the obviously necessary and minor correction of excluding $m=0$ from the message space, which we do hereafter.

The original ElGamal encryption scheme uses as public parameters a large prime $p$ and a primitive element $\alpha$ of $\Bbb Z_p^*$ (the multiplicative group modulo $p$). Thus $x\mapsto \alpha^x\bmod p$ is a bijection over $[1,p)$. Insuring that $p-1$ has a large prime factor makes reversing this function (the Discrete Logarithm Problem) hard.

Recipient B chooses a random secret private key $x_B\in[1,p)$, computes and publishes his public key $y_B=\alpha^{x_B}\bmod p$.

Sender A, wanting to encipher a secret message $m\in[1,p)$ to B, picks a random secret $k\in[1,p)$, computes the secret key $K={y_B}^k\bmod p$, computes $c_1=\alpha^k\bmod p$ then $c_2=K\,m\bmod p$, and sends ciphertext $(c_1,c_2)$ to B.

Recipient B receives $(c_1,c_2)$, and deciphers¹ per $m={c_1}^{p-1-x_B}\,c_2\bmod p$. This works because $K={c_1}^{x_B}\bmod p$.

Observe that given $y=\alpha^x\bmod p$ with $y\in[1,p)$, we can determine with certainty if $x$ is odd or even: we compute $y^{(p-1)/2}\bmod p$ and that's $1$ when $x$ is even, $p-1$ when $x$ is odd. Expressed using the Legendre symbol for $y$ modulo $p$, that's $\left(\frac yp\right)=+1$ when $y^{(p-1)/2}\bmod p=1$ (even $x$), or $\left(\frac yp\right)=-1$ when $y^{(p-1)/2}\bmod p=p-1$ (odd $x$). This allows an adversary to win the IND-CPA game with certainty, by:

Choosing two messages $m_0$ and $m_1$ with $\left(\frac{m_0}p\right)=+1$ and $\left(\frac{m_1}p\right)=-1$. The choice of $m_1=1$ and $m_2=\alpha$ will do, or it can be found by trial and error meaningful messages until two have different Legendre symbols.
Submiting $m_0$ and $m_1$ to the challenger, which picks $b\in\{0,1\}$ at random, sets  $m=m_b$, computes and reveals $(c_1,c_2)$ as above.
Finding $b$ per the following table:
$$\begin{array}{ccc|c}
\left(\frac{y_B}p\right)&\left(\frac{c_1}p\right)&\left(\frac{c_2}p\right)&b\\
\hline
-1&-1&-1&0\\
-1&-1&+1&1\\
\text{any}&+1&-1&1\\
\text{any}&+1&+1&0\\
+1&\text{any}&-1&1\\
+1&\text{any}&+1&0\\
\end{array}$$

This works because $\left(\frac{y_B}p\right)=-1\iff x_B\text{ odd}$ and $\left(\frac{c_1}p\right)=-1\iff k\text{ odd}$. Since $K=\alpha^{x_B\,k}$ that allows to determine $\left(\frac Kp\right)$, which is $-1$ if and only if both $\left(\frac{c_1}p\right)=-1$ and $\left(\frac{c_1}p\right)=-1$. And then $\left(\frac{c_2}p\right)=\left(\frac Kp\right)\,\left(\frac{m_b}p\right)$ allows to conclude on $b$.

Further leaks can occur when $(p-1)/2$ has small prime factors. But when choosing $p$ such that $(p-1)/2$ is prime ($p$ a so-called safe prime), the strategy of restricting to $m$ with $\left(\frac mp\right)=+1$ is believed to make ElGamal encryption IND-CPA secure² against classical computers. That can be done without an iterative process to transform a practical message into a suitable $m$, and back on the decryption side: see poncho's nice squaring technique in comment.

The motivation of using OAEP padding in order to prepare the message to form $m$ in ElGamal encryption are²:

it is non-iterative, and faster than even poncho's nice squaring technique;
it should make ElGlamal encryption IND-CPA secure, because the partial information that may leak won't be enough to allow the adversary to undo the padding;
unless I err once more, it should also make ElGlamal encryption IND-CCA1 secure (but not IND-CCA2 secure for the reason pointed there, even if we add range checks on $c_1$ and $c_2$ on decryption).

But I have no proof for the IND-CPA and IND-CCA1 assertions.

¹ The paper computes $K={c_1}^{x_B}\bmod p$, then asks to "divide $c_2$ by $K$ to recover $m$". That requires computation of a modular inverse, perhaps using the extended Euclidean algorithm.

² The complexity is believed super-polynomial in $\log p$, including in a known dip down in security for $p$ of a special form $r^e\pm s$ with $r$ and $s$ small, which enables SNFS.


Actually there are even more possible options if you use the --expert flag in GnuPG:

$ gpg --expert --gen-key
Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)

As you can see, you can decide to have DSA sign only, but also RSA sign only keys. What's more, DSA keys can also be used as "authentication" subkeys, so you can set your own capabilities for those as well as for the RSA keys (which can also serve for encryption, whereas DSA subkeys cannot)

Now, the difference between a "sign" subkey and an "authentication" one is simply in their respective goals, to allow strong segmentation between signing and authentication processes. The primitive used in both case are the same...
You'll typically use an authentication subkeys for SSH auth (this mainly allows to have your SSH key on a smartcard) and you'll use the signing subkey to sign data. (In the auth case you'll be signing only challenges.)


What is the role of steganography in network security?

I’m not aware of any uses of steganography in network applications, and considering almost all of the networking protocols are open protocols, there’s little room for the application of it. If you need security, you use various forms of encryption.

That being said, the only example I can think of of steganography in modern days is, some printers also printing out some form of a serial code and timestamp in a (almost) hidden part of the printed out material.


Is the CBC weakness in XML Encryption a new discovery? Are other applications vulnerable?

After reading the paper How to Break XML Encryption (thanks to Krzysztof for the link), here are my two cents.

This attack relies on the fact that a CBC-ciphertext C = (IV, C1, ... Cd) can be decomposed into pairs of (IV, C1), (C1, C2), (C2, C3), ... (C(d-1), Cd), each of which is also a valid CBC ciphertext for the same key, relating to the corresponding pieces of plaintext (ignoring padding).

Having such a pair C' = (IV, C1) (for example), we can modify its corresponding plaintext arbitrarily by modifying the initialization vector part.

Now we take an validation oracle - a function to which we can send a pair, and which tells us some information about the plain text. In this attack on XML encryption, the oracle tells us if (a) the plaintext is correctly padded, and (b) does not result in invalid XML (like characters not allowed in XML, or unmatched & or <). Such an oracle can be constructed from the error messages of the attacked web services.

Repeated querying of this oracle with slightly different values of of the initialization vector now allows us to reconstruct the individual bytes of the plaintext.

Some more analysis of the paper is in this blog post Attack of the week: XML Encryption by Matthew Green.

  Does this mean that an attacker can only see a single message,
  or that they can actually infer the encryption key for all messages?

The attack is an attack on the mode of operation - it works for any block cipher in CBC-mode if such a validation oracle can be effectively constructed and used.
It does not give back the key, since it actually circumvents the block cipher instead of attacking it.

It needs a number of oracle queries for each broken plaintext byte (the exact number will on the type of oracle), but can be applied to any intercepted ciphertext message. It also allows constructing ciphertexts with arbitrary plaintext (using more such oracle queries).

  Is this a new vulnerability in CBC?

From the introduction, it seems that similar attacks on other protocols using CBC-mode (attacking the padding scheme instead of the encoding like here) were already known before (as early as 2002). The fact that CBC-messages can be decomposed as shown above is certainly not a new insight.

But this specific way of breaking seems new (it was discovered in February 2011, they just waited a bit with writing and publishing the paper).

  How is this relate to pre-existing applications that use CBC?

Protocols like TLS, SSH and IPSec combine the encryption with a message authentication code for integrity/authentication (or even use a combined "authenticated encryption" scheme). A chosen-ciphertext attacker (like here) has usually no way of constructing a valid MAC tag, and if the application rejects messages with a wrong MAC instead of trying to parse the plaintext (and giving a suitable error message), there should be no problem.

XML Encryption also provides for a MAC, but it is optional - in a way that allows an attacker to strip off the MAC and still get a valid encrypted message.

For file or email encryption (like PGP), there is usually a key per message, and no easy way of using an validation oracle.


Padding always the same, problem or not?

No, it is not a problem to have the same padding at the end of a message. Some known plaintext is often available in practice (protocol fields, etc). The security of the system is (or at least should be) based entirely on the key.

If you are really worried about it for some reason just change the IV for each 64-byte block. Or as CodesInChaos said in a comment, if messages are always a multiple of 16 bytes, don't even use padding.


Why are the indicator drums of a Bombe machine labelled from A to Z clockwise?

I emailed someone, and it turns out that the rotor positions found by the Bombe are used as the ring setting in the checking machine. Because the ring setting is the "negative" of the rotor position, the indicator drums spin backwards, so that it shows the correct ring setting that corresponds to the rotor positions for the checking machine.


Is using the same key for different message HMACs insecure?

No, with a reasonable choice of hash function, HMAC can safely authenticate many messages under the same key—it is not a one-time MAC like GHASH or Poly1305.  Of course, it may be prudent to use a message sequence number so you can reject replays (and it may be necessary for your encryption scheme, e.g. if you're using AES-CTR or ChaCha).

That said, why are you making this decision instead of using an authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305?


Best attack on double DES followed by XOR with third key

I cannot think of how to attack this using exactly the same resources as the classic meet-in-the-middle attack against double-DES, but there is a way to solve it with similar computational and memory resources (i.e. with about $2^{57}$ time and memory), but using $2^{56}$ chosen plaintexts and $2^{56}$ (adaptive) chosen ciphertexts.

First, notice that if we ask for the encryption of $m$, xor the ciphertext with a known constant $T$, and then ask for the decryption of $E_k(m) \oplus T$, the following equality holds:
$$E_k^{-1}(E_k(m) \oplus T) = DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus k3 \oplus T \oplus k3))$$
$$= DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus T))$$
So we don't have to worry about the third key, and now we only need to figure out how to conduct a MitM attack against that construction using four applications of DES and two keys.  We are going to do this in an inside-out fashion.

Step one: pick any 64-bit value, $A$, and for all $2^{56}$ possible candidate values of $k2$ (which I will denote $k2^*$), do the following:

compute $B = DES_{k2^*}^{-1}(A)$,
request $C = E_k(B)$,
request $D = E_k^{-1}(C \oplus T)$.
compute $F = DES_{k2^*}(D)$.

Store all $2^{56}$ values of $F$ in a hash table, along with the $k2^*$ candidate values associated with each.

Step two: For all $2^{56}$ possible candidate values of $k1$ (denoted $k1^*$), do the following:

compute $G = DES_{k1^*}^{-1}(DES_{k1^*}(A) \oplus T)$,
check if there is any $F$ such that $F = G$.

Any such collision will 'suggest' that $k1 = k1^*$ and $k2 = k2^*$ (the stored $k2^*$ candidate value for $F$), a suggestion that can be easily tested in the following manner:

If you know $m$, $m'$, and $E_k(m)$ and $E_k(m')$, then compute $DES_{k1^*}(DES_{k2^*}(m)) \oplus DES_{k1^*}(DES_{k2^*}(m'))$ and check if that equals $E_k(m) \oplus E_k(m')$.  If so, then you almost certainly have the right keys.  From there, $k3$ is trivially deducible.


Proving multiple products "in the exponent"

Unfortunately, improving over the $O(n)$ solution seems to require the use of non-standard assumption. More precisely:

No, Groth-Sahai NIZKs cannot be used for proving this statement with communication less than $O(n)$, because the witness held by the prover is already of size $O(n)$. In fact, even if the prover knew all the discrete logarithms of the group elements (i.e., all the $a_i$'s), Groth-Sahai proofs would still produce proofs of size $O(n)$. The main reason for this is that Groth-Sahai proofs are... Well, proofs (more precisely, they can be either proofs or arguments, depending of the mode of the crs, but they have the same size in both cases since the modes must be indistinguishable). An interactive proof (meaning, with statistical soundness - as opposed to interactive arguments which have computational soundness), zero-knowledge or not, non-interactive or not, cannot have communication sublinear in the witness size unless NP can be decided in subexponential time.
It does not seem to be straightforward to obtain a shorter proof for your problem without using "heavy hammer" tools, or the random oracle model. If you are ok with using the random oracle model, then there are sublinear interactive proofs which can prove this statement with logarithmic communication complexity, and can be made non-interactive using Fiat-Shamir (1, 2). In fact, very recently, it was shown here how to build such succinct interactive public-coin arguments directly for bilinear equations a la Groth-Sahai. If you do not want to use random oracles, then you will have to rely on the non-standard and non-falsifiable assumptions underlying the constructions of all SNARGs - there are many available. However, none of them will provide a very good concrete efficiency for your specific problem, and I'd strongly suggest to rely on a solution in the random oracle model instead.


How to do division using Beaver Multiplication Triples

There exists a number of general multiparty protocols that can securely compute any function. Some of these, for instance SPDZ and this one, use Beaver triples. These protocols can compute integer division, since integer division is a function.

However, using general multiparty protocols may not be the most practical or efficient. So there has also been some research in specialized protocols for integer division. There is e.g. a paper describing a secure two-party protocol for integer division here. The "related work" section in that paper contains references to other integer division protocols for more than two parties. I'm not sure any of these protocols use Beaver triples, though.


SHA-1 – Why is it hard to find a certificate collision?

Why is it it’s so much harder to execute a successful collision on certificates than it is on text data?

It's not.  Actually, the attacker does have to worry about the sequence number that the CA will use, however as we seen from the successful MD5 attacks, that's a solvable problem.

What's more difficult is coming up with a useful (to the attacker) collision.

If all we want is to generate two colliding certificates signed with SHA-1, we can take advantage of the fact that RSA certificates have some random-looking data in the middle (the "RSA public key"), and a nontrivial percent of random moduli are easy to factor (and hence is easy to find the corresponding private key).  So, all we'd need to do is a) guess the initial parts of the certificate (already solved problem), b) generate a collision in the initial parts of the RSA modulus, giving us two top portions and c) then search for a common lower section of the modulus where we can factor both.  Then, we can have the CA sign one (which requires us to have the private key, which w do), and then we can use the other (which also requires us to have that private key, which we do).  Bingo, we have a collision.

However, it's not a useful collision; all we've done is use one modulus with the CA, and another in practice; that doesn't allow the attacker to, well, attack anything.

What the attacker really wants is to have the CA sign one certificate for 'innocent1.com', and then have the certifcate for, say, 'microsoft.com' and hashes to the same value (and so they can use the same signature in that certificate).  To do that, the attacker needs to form two certificate prefixes (one with innocent1.com, and the other with microsoft.com), and form a collision where the two hash states join together to form a common one.

So, what the collision method needs to do is, instead of starting from a common state (and finding two distinct sets of blocks that both result in a common state), start with two predetermined hash states, and find a set of blocks that shepherd them into a common state.  We know how to do this with MD5; the current attacks on SHA-1 doesn't do this.

Now, it wouldn't be prudent to assume that the attacks on SHA-1 couldn't be extended to do that.

  No collision can be made after the certificate has been generated

True (even for MD5 certificates); however the base SHA-1 attack was published 10 years ago.  It's only now that someone has published that they actually performed the attack, however that doesn't mean that someone else didn't do it first.

  All CA’s only issue SHA-2 certificates

I've been told (thanks Ajedi32) that CA's only issue SHA-2 (or better) certificates now; however that doesn't address certificates in the field that haven't expired yet.  Yes, you can't attack them now; you could attack them a year ago...

Also:

  I assume this has to do with the fact the certificate actually is a file that contains signed (and therefore encrypted) data.

Actually, a certificate does not include any encrypted data (ASN.1 encoding doesn't quite count as encryption :-).  Because anyone is supposed to be able to parse a certificate, it can't include any encrypted (unintelligible without the key) data.


Algorithm to securely exchange identities

The Simple Protocol:

Alice generates a signature key pair (to sign in step 4, all other signatures in the protocol will be from the original key pairs), calculates its encryption under each of the other participant's public keys, indicates which encryption corresponds to which key, and then signs and posts the result.
The other three participants each decrypt the message encrypted with their public key, calculate the encryption of that under the public keys belonging to the other two of those three participants, indicate which encryption corresponds to which key, and then sign and post the result.
(With signed messages) Those three participants confirm that they got the same signature key pair from all three sources, and then all four participants agree on a time period for step 4.
Each participant generates a new key pair, and posts the public key along with its signature under [the signature key pair from step 1].
Once four posts with a public key and its signature under [the signature key pair from step 1] have appeared, each participant posts a signed confirmation, with the lexicographically sorted list of those four messages, that their public key was the public key in one of those messages.
After each participant has confirmed in step 5 (and made sure the lists of messages match), use the public keys from step 4.

The potential problem is that a participant can trivially force an abort with zero chance of getting

caught. $\:$ Every way I can think of for this loses the property that the [honest participant]-[key pair] relations will be forever hidden from an attacker who doesn't break the cryptosystem before

the protocol ends (long-term security for all participants). $\:$ The best way I can think of is:

(With all messages signed),
Use generic multi-party computation to compute the lexicographically sorted list of a new public key from each party. $\:$ This requires oblivious transfer, and I have no idea how many of them it will need. $\:$ This does not need any anonymous posts, and works against any number of disruptive participants.  Depending on what oblivious transfer protocol is used, this might provide long-term security for one of the participants.


Shouldn't the other parameters have exactly the same requirements?

Certainly not all other parameters. The vendor could set requirements for $e$, but they would be different. For the other key parameters, extra requirements would be unusual, and there could be a valid technical reason for them only if you are using gear (software or hardware) that the vendor supplied or prescribed for use when signing binaries or preparing a Certificate Signing Request.

The key parameters given to the vendor or which will get into the POS are those in the public part of the RSA key: $(N,e)$. There are legitimate interoperability requirements for these. However, the requirement "very first byte of the Modulus ($N$) of the private key is greater than 0x80" is not standard: it should be "..is not lower than 0x80", or it is there to work around some nasty bug, or it is a non-standard flag for something (e.g. allowing loading unsigned code when the first byte of $N$ is 0x80). The standard (FIPS 186-4 appendix B.3) requirement on $N$ for 2048-bit RSA key is $2^{2047}\le N<2^{2048}$ (and $N$ odd), not $2^{2047}+2^{2040}\le N<2^{2048}$, and I would not let that deviation unexplained.

The standard for $e$ is $2^{16}<e<2^{256}$ (and $e$ odd), with the upper limit often lower, but there's nothing common or reasonable that would require the first byte to be over a limit close to 0x80. $e=2^{16}+1$ is sometime required. $e=3$ was formerly popular in POS applications, for it speeds up card authentication and is perfectly fine when used with proper signature padding.

A private key should remain known by its legitimate holder only, and (for RSA and secure keys) there is no way to assess the value of its parameters from what should get known to the vendor or manipulated by the POS devices. Even the fact that $N$ has two rather than three prime factors is not testable by the vendor or POS. Thus a requirement on the private key is technically justifiable only for gear that uses the private key (in the application: to sign software or CSR). Starting with the more commonly enforced (list not limitative):

The private key is expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ per RSAPrivateKey in PKCS#1 v2.2 without the optional otherPrimeInfos, and thus $N$ has exactly two prime factors, rather than more.
$N$ has exactly $k$ bits with $k$ in a discrete set (typically: multiples of some power of two in some range).
$d<(p-1)(q-1)/\gcd(p-1,q-1)$ (limit in FIPS 186-4). That's often relaxed to $d<N$ (limit in PKCS#1v2.2), $d<2^k$, or other.
$p$ and $q$ are odd and in range $(2^\frac{k-1}2,2^\frac k2)$. When enforced, the lower limit may vary, e.g. be relaxed to $\mathtt{B5_h}\,2^{\frac k2-8}$ or $2^{\frac k2-1}$. But even if such limits are standard, many hardware devices and most software are perfectly happy with $p$ and $q$ not of the same bit size.
$q<p$ or vice versa (a requirement indicative of lousy practice).


Security of traditional ORAMs if write accesses are revealed

The adversary will not be able to distinguish between that access pattern and any other with the same volume and timing.


Encrypting a string of arbitrary size with a big integer

When you use Diffie-Hellman key agreement protocol, both sides reach the equal keys. Then, you can use it with private key encryption methods, not public ones (like AES or one-time-pad).

One philosophy of public key encryptions is for avoiding key exchanges or key agreements. They are also called asymmetric encryption methods, because the sender and the receiver of the messages have different keys.


Regarding Lattice atttacks on ECDSA with a portion of known bits of the nonce k

The constant is derived from the so-called Gaussian Heuristic, which is used to predict the expected length of the shortest vector of a random lattice. For the attack to work, one must ensure that the special vector that he is looking for will be the shortest, so that it can be found. We therefore compare the length of that to-be-found vector with the expected length of the shortest lattice vector.


Why is the discrete logarithm problem assumed to be hard?

While $O(n)$ is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in $O(n)$ but instead in $O(\log(n)) =  O(|n|)$ (e.g. expoentiation with square and multiply has $|n|$ multiplications and at most $|n|$ squaring operations).

Therefore, the basic consideration for $n$ should not be the number of group elements, but its logarithm (which is linear to the length of the numbers. In order to avoid the question: This is valid for any numeral system, regardless of its base). So if we have numbers of a group $\mathbb{G}$, we should set $n=\log_2|\mathbb{G}|$, and brute force algorithms require $O(2^n)$ operations.

Short version with less algebra:

Encrypting or signing something uses exponentiation as operation, and there are algorithms with complexity linear to the length of the numbers (in binary representation), and let's call the length $n$. If you want to test all possible values (aka brute force), there are $\approx2^n$ values to test, and this is exponential in the parameter $n$.


Number of generators of an elliptic curve

No, he really means the number of points on $E$. So the number of solutions to the given equation plus 1 (for the point at infinity). He also gives the answer as $25.$

You need to apply your idea about number of generators to the correct group size.


What use is the signature without the message under RSA?

Caution: the question assumes that the message $m$ can be larger than the public modulus $N$ and sent separately from the signature (perhaps, encrypted), contrary to textbook RSA as in the original article. The answer makes that assumption unless otherwise specified.

If we signed a secret message $m$ by publishing its signature $σ$ computed as $m^d\bmod N$, at least two very bad things would happen:

The message would not be so secret anymore
That's because anyone knows the public key $(N,e)$, and thus from $σ$ can compute $σ^e\bmod N$, which is $m\bmod N$. This reveals a lot of information about $m$, which goes straight against the requirement to keep $m$ secret. In modern cryptography, the adversary succeeds if she learns anything about a secret message (except its length), and $m\bmod N$ qualifies. For example:

$m\bmod N$ allows (with overwhelming odds) to recognize $m$ among a moderate list of arbitrary messages.
If $m$ is shorter than $N$ then $m\bmod N$ is $m$ and thus $m$ is no longer secret at all (this occurs when $m$ is less than $256$ bytes for $2048$-bit $N$, a common size).
If (as in the question) it is computed and published the signature $σ'$ of the same $m$ according to a different RSA key $(N',e')$, then this reveals $m\bmod N'$. By the Chineese Remainder Theorem we can efficiently compute $m\bmod(N\;N')$, and this reveals $m$ if it's size is less than the sum of the size of $N$ and $N'$, extending the above to longer messages than was possible with a single signature.
If $m$ is known except for a segment shorter than $N$ (that is $m=m_0\mathbin\|m_1\mathbin\|m_2$ with $m_0$ and $m_2$ known, and $m_1$ shorter than $N$), from $m\bmod N$ it is easy to find $m_1$, thus $m$, as follows: if $|m_i|$ is the number of bits in each segment of $m$, we have $m\bmod N=\big((m_0 2^{|m_1|}+m_1)2^{|m_2|}+m_2\big)\bmod N$ thus $m_1=\big((m\bmod N)-m_0 2^{|m_1|+|m_2|}-m_2\big)2^{-|m_1|}\bmod N$ where $2^{-|m_1|}$ is the multiplicative inverse of $2^{|m_1|}$ modulo $N$, which is easily computed using the Extended Euclidian algorithm.

It would be easy to make forgeries
In particular, it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, $N$ and $e$, it is easy to exhibit $m_1$ such that $m=m_0\mathbin\|m_1$ verifies $\sigma^e \equiv m \pmod N$. Just choose $m_0$ ending with a terminating 0x00 bytes, decide a size $b$ of $m_1$ with $b$ multiple of 8 and $2^b>N$, pick any $\sigma$, compute $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$ ).

Note: in common textbook RSA, $m$ is not sent separately and is recovered as $m\gets\sigma^e\bmod N$, hence $0\le m<N$. This makes the attack more difficult. However for small $e$, and when $|m_0|$ is small enough (roughly up to $\log_2(N/e)/e$ bit including terminating 0x00), we find $b\gets8\,\lfloor \log_2(N/(m_0+1))/8\rfloor$, compute $σ\gets\left\lceil\sqrt[e]{m_0\,2^b}\right\rceil$ and $m\gets σ^e$. This $σ$ verifies as the signature for this $m$, and prints the same as $m_0$.

Rather, good and common practice in order to RSA-sign a confidential message is to:

Encrypt and sign (or sign and encrypt)
Encipher the message (typically using a symmetric algorithm such as AES in CTR mode with random IV), then RSA-sign the cryptogram (ciphertext, rather than the plaintext), e.g. as in 2 below; or transform the message into a signed message (again e.g. as in 2 below), then encipher that whole signed message.Note: if possible, use encrypt-then-sign. If for some reason sign-then-encrypt must be used, make sure to encrypt the signature even if it is randomized; pay care that deciphering of any invalid ciphertext can not trigger undesirable behavior on the receiver side; and pay care that signature verification of partially invalid messages does not leak information about the message.

(and) Use a signature scheme with hash-based padding
In order to RSA-sign a message $m$ (confidential or not), signature must NOT be computed as $σ=m^d\bmod N$, which would be an unsafe use of textbook RSA. Rather, one might (there are other secure ways)

compute $h=H(m)$ for some hash function $H$ like SHA-256, with $h$ what will actually be signed (albeit still not using textbook RSA, as it could be vulnerable to forgery if the adversary could obtain the signature of chosen messages)
appropriately pad $h$ into a so-called message-representative $r$ with $0<r<N$ by some method (possibly involving adding randomness), the most common such methods being RSASSA-PSS and RSASSA-PKCS1-v1_5 in PKCS#1;
compute the signature as $σ=r^d\bmod N$
build the signed message as $m\|σ$ (that is, append the signature); the verifier will extract $m$ and $σ$ from $m\|σ$, compute $h=H(m)$, compute $r=σ^e\bmod N$, and check $r$ against $h$ according to the padding method.


What pieces of information do you need to unhash a key to find out the original message?

You can't reverse a hash, because hash functions are one-way-functions by design. The best you can do is brute-forcing, meaning you try every input until you get the same hash-value and even then you can't be sure if you have found a hash-collision or the original message.


Most protocols use a randomly generated key (TLS, for example) that spans the full keyspace of the cipher, so 128-bits in the case of AES-128.

For other uses where the cipher key is directly obtained from a plaintext password a propper key derivation procedure should be used. One standard for this is PKBDF2 which, in simple terms, computes the cipher key by repeated application (tens or hundreds of thousands of iterations) of a hash function to slow down the calculation in order to make brute force attacks impractical.

Imagine a key derivation function that consisted of just two applications of a hash function and compare this to deriving a key from a single hash function application. In this case it is twice as computationaly expensive to mount a bruteforce attack on the password, and this corresponds to an extra bit of the password key. In this way it is possible to "trade" time for key bits.


How can homomorphic encryption be probabilistic while allowing for math to be conducted?

Probabilistic encryption is a necessity for ANY public-key encryption scheme. The reason is that in such schemes anybody can perform the encryption, thus if the encryption was deterministic, that would allow to check a guess of the plaintext. That would be a total disaster in a lot of applications: enciphering a coin toss, a name on the class roll, a price, a bulletin vote, a credit card number or SSN, a password..

There's a tantalizingly simple but somewhat oversimplified explanation to:

  If a probabilistic encryption algorithm is used, how does decryption return the correct message?

That explanation says that encryption takes the message, combines it with randomness, then enciphers; and decryption deciphers, then remove randomness to get the original message. That's exactly how it is done in RSA encryption with random padding, where combines sometime is as simple as appending randomness and fixed bits to the message (see e.g. RSAES-PKCS1-V1_5).

However, that simple explanation falls short of the goals of homomorphic encryption, because (as noted in the question) it does not yield a method to perform arithmetic on the encrypted message without holding the decryption key. That's why RSA encryption with random padding is not homomorphic, when RSA without padding is (multiplicatively, modulo the public modulus).

Secure homomorphic encryptions schemes do combine the message and the randomness as in the oversimplified explanation, but that combination is not by concatenation. For homomorphic randomized encryption to work, the combination of randomness and message must be by a method precisely matching the rest of the scheme.

The Paillier cryptosystem is one of the simplest example of randomness combination giving both security and homomorphicity.

As for a normal public-key encryption system, encryption requires the public key of the entity that will ultimately decipher. But (as the name implies) that public key is not secret. In Pailler, it is $(n,g)$ with large $n$ difficult to factor (similar to RSA) and choice of $g$ with $g^n\bmod n^2=1$ (typically $g=n+1$). Pailler encrypts message $m$ with $0\le m<n$ into $$E(m)=g^m\,r^n\bmod n^2\quad=c$$ where $r$ is a fresh random with $0<r<n$ and $\gcd(r,n)=1$.

Efficient decryption is possible knowing the factorization of $n$, with $D(E(m))=m$ for all valid $m$ and $r$.

That way of combining message $m$, randomness $r$, and public key $(n,g)$ is such that we have a homomorphic property:
$$\begin{array}{llll}
E(m_0)E(m_1)\bmod n^2&=g^{m_0}\,{r_0}^n&g^{m_1}\,{r_1}^n&\bmod n^2\\
&=g^{m_0+m_1}&{(r_0\,r_1)}^n&\bmod n^2\\
&=g^{(m_0+m_1\bmod n)+w\,n}&((r_0\,r_1\bmod n)+x\,n)^n&\bmod n^2\\
&=g^{m_0+m_1\bmod n}\,{(g^n)}^w&{(r_0\,r_1\bmod n)}^n&\bmod n^2\\
&=g^{m_0+m_1\bmod n}&{(r_0\,r_1\bmod n)}^n&\bmod n^2
\end{array}$$
$w$ and $x$ are integers bound to exist, that disappear later in the calculation. On the left side, that's by choice of $g$. On the right side, that's because the polynomial in $x$ raised to the power $n$ has all non-constant terms multiple of $n^2$.

We see that $E(m_0)E(m_1)\bmod n^2$ is identical to what the encryption of $m=m_0+m_1\bmod n$ could have been for choice of randomness $r=r_0\,r_1\bmod n$ .
Notice that the requirements $0\le m<n$ , $0<r<n$ and $\gcd(r,n)=1$ are met.

For a working decryption, we must thus have
$$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1\bmod n$$
or, for regular addition: if $0\le m_0<n/2$ and $0\le m_1<n/2$ then
$$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1$$

To produce a cryptogram per that homomorphic property, one needs

at least one ciphertext $c_0=E(m_0)$ for an unknown message $m_0$, typically prepared by someone else (otherwise why use homomorphic encryption?)
either

A second similar $c_1=E(m_1)$, so as to be able to compute the ordinary product $c_0\, c_1=c$
A new $m_1$ to combine, and the public key, which allows to compute $c_1$ and be back to the previous option.

Typically at least, the public key (specifically, it's component $n$), to allows reduction of $c_1\,c_2$ modulo $n$, for two reasons

concealing if a particular $c_i$ was involved in preparation of the ciphertext (otherwise determinable by testing if $c_i$ divides $c$)
the reduced $c\bmod n^2$ is shorter than $c$ by a factor about 2.


The certificates are generated in full by the CA, combining the data from the CSR (e.g. CN) with data from the CA (e.g. serial number, issue date etc.).

The signature of the CSR - which is also signed - is by the private key that is part of the key pair of which the public key is within the CSR. This signature value is verified and disposed.

The CSR, which is mostly kept in a key store together with the private key gets replaced by the returned certificate, which is signed by the CA, which is identified as the issuer in the certificate.

Notes / discrepancies:

The hashing and padding is specific and internal to the PKCS#1 v1.5 RSA signature generation (some libraries also accept hash values or hash functions though).
It is not possible to encrypt with a private key because anybody can "decrypt" with the public key; the private key is used for RSA modular exponentiation though.
The certificate signature value is the value after modular exponentiation, it is of course not just the hash value.
The CSR is a certificate signing request which is/was defined in PKCS#10, it is not a certificate by itself even if it has a lot in common with a certificate.
As mentioned, the CSR is signed.
SHA-256 has an output size of 256 bits, not 160 bits (are you kidding me?)
Using SHA-512 and PSS signature generation would increase security, but not as much as increasing the key size: a 2048 bit key pair is relatively  small nowadays.

All and all, the general idea and the components of the TBS Certificate part of the certificate are correct but all the details are wrong in that picture.


You are correct.  This is mentioned somewhat obliquely at the beginning of §9 ‘Security considerations’:

  If the external security layer used to protect the SCRAM exchange
     uses an anonymous key exchange, then the SCRAM channel binding
     mechanism can be used to detect a man-in-the-middle attack on the
     security layer and cause the authentication to fail as a result.
     However, the man-in-the-middle attacker will have gained sufficient
     information to mount an offline dictionary or brute-force attack.

Thus, you should really avoid using SCRAM to authenticate the server to the client.  You might prefer to look into a password-authenticated key exchange like SRP or SPAKE2+ instead.


Difference between “ECDH with cofactor key” and “ECDH without cofactor key”?

First, a bit of background.  If we refer to the size of an elliptic curve group as $n$, we select an elliptic curve with $n = hq$, where $q$ is a large prime, and $h$ is a small integer called the cofactor; it is typically either 1, 4 or 8.  The values of $q$ and $h$ will be part of the curve definition.

As you know, with straight DH, we agree on a point $G$, Alice selects a random value $a$ and computes $aG$; Bob selects a random value $b$ and computes $bG$; they exchange values, and then Alice computes $a(bG)$, Bob computes $b(aG)$, and those are the same value.

When we use the cofactor variant of DH, the first part is exactly the same; Alice selects a random value $a$ and computes $aG$; Bob selects a random value $b$ and computes $bG$; they exchange values.  However, Alice then computes $ha(bG)$, and Bob computes $hb(aG)$.  That is, in the second phase, they internally multiply their random value by $h$ before doing the point multiplication.

Why do they do this?  Well, it helps avoid a small potential data leakage if Bob doesn't play by the rules.  If $h>1$, there are points with small order, we'll call such a point $H$ (there won't always be a point of order $h$, however to make this argument slightly simpler, we'll assume there is).  Then, suppose an attacker didn't give Alice the value $bG$, he gave him the value $bG+H$.  Alice would then compute $a(bG+H) = abG + aH = abG + (a \bmod h)H$.  As Bob knows the value $abG$ (he does his half of the second phase honestly), he can compute Alice's shared secret with $h$ different alternatives, and so recover $a \bmod h$.

By internally multiplying by $h$ in the second phase, this doesn't happen; we have $ah(bG+H) = abhG + ahH = abhG$ (as the point $H$ is of order $h$), independent of what $a \bmod h$ is.

This isn't the only possible way to defend against this; Alice could also compute $q(bG)$, and verify that it's the point at infinity ($q(bG + H)$ won't be), however that's fairly expensive, while the cofactor method just uses two or three point doublings over the computations we would be doing for ECDH anyways.

Now, if this is the only place that Alice uses $a$ (that is, if she is using ephemeral ECDH), this leakage doesn't matter a bit - Bob already knows the shared secret, and he can't leverage that into any knowledge of any other secret.  However, if Alice reuses her $a, aG$ pair for other exchanges, the leakage is there (and whether it's enough to worry about is another question entirely).

One last word of warning: when we compute the value $(ab)G$, we typically actually compute $(ab \pmod q)G$, as normally they're the same (and computing things $\bmod q$ makes things more efficient).  However, this is one place where we don't; we really do formally compute $(ah)bG$, even if $ah > q$.


Secretless authentication method for remote hardware

What is the purpose of integrating a Secure Element or Secure Access Module to address the needs of secret storage for an infrastructure if it requires another secret for connection?

One can be quite sure that the genuine Secure Element is involved in a communication that it certifies. If the Secure Element is BGA-mounted and/or epoxy-bounded to a PCB, one can be reasonably confident that this PCB is involved, or that adversaries spent significant effort to workaround that.

  Is there any authentication method that would not require secret, but would guarantee anyway identities?

Not in traditional cryptography, including asymmetric and post-quantum.

Physically Unclonable Functions aim at something close: the PUF is supposed to be impossible to analyse to a degree allowing its successful cloning. One should be reasonably sure that a PUF was involved in a communication that it certifies. If the PUF is integrated on a silicon die, that die was involved too. That's the general idea when the PUF aims at preventing unauthorized production of the die from unmodified photomasks (stolen or reverse-engineered), and/or make the die unclonable.


Check out the notes of paragraph 9.2 of that document, it lists all the encodings in hexadecimal values. It does so for PKCS#1 v1.5 padding for signature generation, but it certainly contains the OID's internally - 06 LL { OID } where LL species the length of the BER encoded OID:

For the six hash functions mentioned in Appendix B.1, the DER
encoding T of the DigestInfo value is equal to the following:

  MD2:     (0x) 30 20  30 0c  06 08 2a 86 48 86 f7 0d 02 02  05 00  04 10 || H.
  MD5:     (0x) 30 20  30 0c  06 08 2a 86 48 86 f7 0d 02 05  05 00  04 10 || H.
  SHA-1:   (0x) 30 21  30 09  06 05 2b 0e 03 02 1a 05 00  04 14 || H.
  SHA-256: (0x) 30 31  30 0d  06 09 60 86 48 01 65 03 04 02 01  05 00 04  20 || H.
  SHA-384: (0x) 30 41  30 0d  06 09 60 86 48 01 65 03 04 02 02  05 00 04  30 || H.
  SHA-512: (0x) 30 51  30 0d  06 09 60 86 48 01 65 03 04 02 03  05 00 04  40 || H.

I'll add SHA-224:
  SHA-224: (0x) 30 2D 30 0D 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1C || H.

where || is concatenation and H is the hash value.

The ASN.1 syntax is officially defined in

ISO/IEC 8824: Information technology - Abstract Syntax Notation One (ASN.1): Information object specification

and the BER/DER method of encoding that is applied is specified in

ISO/IEC 8825-1:  Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)

And the OID encoding is in paragraph 8.19 for the 2010 version of that document (an errata exists). How to actually encode it is explained in this answer on StackOverflow


zk-SNARKs vs. Zk-STARKs vs. Bulletproofs: definitions

A class. Parameters according to which it is standard to compare them, are: prover time, verifier time, proof size, requirement of trusted setup, cryptographic assumptions. For "succinctness", the standard definition requires that verification time is sub-linear and proofs are "small".
STARK however, is a name of a specific zk-SNARKS protocol, see any Eli Ben Sasson talk on Youtube for the specific attributes.
I reckon it's because verification time is linear.


The inverse in AES is defined over a particular field. All the operation are done in this field.
The Rijndael finite field is defined as follow: $GF(2^8) = GF(2)[x]/(x^8 + x^4 + x^3 + x + 1)$.

The "numbers" are a representation of polynomials (a byte represents coefficients of a polynomial):

0x95 = 1001 0101 = $x^7+x^4 + x^2 + 1$

0x8A = 1000 1010 = $x^7+ x^3 + x$

And the product of the two polynomial reduced modulo the irreductible polynomial is 1, as expected.

There are several way to implement the inversion and the affine transformation described in the AES to get the final SBox. Once you get the math, you may choose one way or the other, keep in mind that you can avoid to implement all the algebraic structure and a function taking as input only a byte (cfr: https://en.wikipedia.org/wiki/Rijndael_S-box#Alternate_equation_for_the_affine_transformation)

You may find more information here: https://en.wikipedia.org/wiki/Rijndael_S-box and https://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael.27s_finite_field and Galois fields in cryptography


Cryptanalysis to reverse engineer a hash?

You are correct that it is a "bad hash". In fact it is not a hash at all. I've worked at a company that used a slightly different scheme for obfuscating database keys/numbers in URLs. And I also worked for another company that used a scheme that looked surprisingly similar for unlock codes for electronic devices.

The formula for converting "hashes" back into inputs looks like:

Take the "hash" (column "hash" below") and use your substitution cipher (E goes to 1, etc) to turn it into hex (column "subs" below).
Convert the result into decimal (column "to dec" below).
You have an 8 digit number, swap the first and last half of the digits (column "swap" below).
Divide the result in 3 by 13 to obtain the customer id (column "divide" below).

"hash".....subs......to dec......swap.....divide
EHELKHE - 1418741 - 21071681 - 16812107 - 1293239
ILZXFZF - 58FD2F2 - 93311730 - 17309331 - 1331487
IKYJXWH - 57E6DC4 - 92171716 - 17169217 - 1320709
GUVUMMY - 3ABA99E - 61581726 - 17266158 - 1328166
HFXLFYZ - 42D82EF - 70091503 - 15037009 - 1156693
ELHZLZV - 184F8FB - 25491707 - 17072549 - 1313273
GKDMWGM - 3709C39 - 57711673 - 16735771 - 1287367
EHDHYYF - 1404EE2 - 20991714 - 17142099 - 1318623

For folks who might find this in the future, it helps to make a spreadsheet and multiplication tables (customer id * 1 through customer id * 50). Formulas like these are usually simple linear formulas like $mx + b$, sometimes with a modulo involved (such as $mx + b \mod c$). And sometimes with "junk" digits added to make things harder to reverse engineer.

D.W.'s idea of "chosen plaintext" attack is also a good one. If you had pairs of customer id and "hashes" that varied by a single digit in the customer id, that would probably make it easier to attack.

And "security by obscurity" is no security at all. I spent about 2 hours avoiding homework tonight.


This homework is about constructing a tiny finite Elliptic Curve group over a prime finite field, then showing Diffie-Hellman key exchange on that.
It's needed to understand

Modular arithmetic$\pmod p$, that is computation (including division) in the finite field of integers modulo $p$ (here $p=223$ but the same techniques apply for any prime $p$).
The notion of set of pairs $(x,y)$ matching an equation $y^2 = x^3 + a\,x + b $ in that finite field.
Under some conditions on constants $a$ and $b$, construction of a finite Elliptic Curve group on that set (with one extra identity element added). With the problem as we get it, it must be used $b=9$, and $a$ is left at the discretion of the reader.
The notion of order of a group/curve, and of order of an element in the group (a perfect generator is to be understood as an element of order the order of the group; equivalently, adding the element to itself repeatedly reaches every element of the group).
Diffie-Hellman key exchange on an arbitrary finite group with a states generator. That's the easy part. "Use $X_A = 8, X_B = 15$" is to be used in that part only; that would be the values chosen by parties.

Because $p$ is so small, it's possible to get away with explicitly finding the points $(x,y)$ forming the (non-neutral) elements of the group. In actual cryptography, we'd get say $p\approx2^{256}$ and about as many points, thus point counting would probably use the Schoof–Elkies–Atkin algorithm, that many users of crypto, including me, have never actually studied.


Fiat-Shamir vs Common Reference String to make NIZK

Since there are no answers here yet, I'll write down my own opinion.

The Fiat-Shamir heuristic for augmenting Sigma-protocols (or possibly any 3-move honest-verifier ZKPoK?) works as follows: For the problem statement $X$ and first prover message $A$, the prover self-generates the challenge $e = H(X,A)$and uses it to generate its final response $z$. Note that these proofs can be replayed.
In Damgard's paper “Efficient Concurrent Zero-Knowledge in the Auxiliary String Model” the Common Reference String model is used to generate a trapdoor commitment scheme, enabling the verifier to simulate a proof and thus guaranteeing zero-knowledge. In this setting, since the prover still actively participates in the protocol and Special Soundness is assumed, the prover cannot cheat.

To me it seems that your conjecture is true. Given a collision-resistant hash function $H$ (a criterion I think a PRF satisfies), digesting $A$ and the common reference string together should derive a ZKPoK out of a Sigma Protocol. But the thing is, that string should only be unique, and it is solely in the interest of the verifier that it be so. Therefore even a malicious verifier can be trusted to provide it properly, and the overhead of a CRS setup having to generate unique strings can be avoided.


Oblivious transfer where neither party learns the index of the message

The simplest way to do this would be to have the sender randomly shuffle the elements. The receiver chooses a random element to request. That way the receiver has no idea which of the original (before the shuffle) elements he got.


The former. Maximum output must be <= 255*HashLen. So for SHA256 which has a digest of 32 bytes, max HKDF output would be <= 8160 bytes. For SHA512 which has a digest of 64 bytes, max output must be <= 16320 bytes. I can't imagine you would need a key longer than 8160 bytes. If you require multiple keys you can use the 'info' parameter for different contexts/keys from the same PRK.


(Lightweight) Multicast one-way Authentication

Yes, the problem of multicast one-way authentication can be solved using symmetric cryptography only, assuming (at least) one of the following applies (there might be other ways):

we trust each receiving party to hold a common secret key secret, and not to use it nefariously;
we accept overhead in the broadcasted message growing linearly with the number $n$ of recipients, in the order of $n\cdot b$ bits for $2^{-b}$ odds of forgery;
the broadcaster and receivers share some time reference, and we can tolerate a delay (a small multiple of the time uncertainty) for the authentication of a message.

In all cases, the general idea is to include with the message a Message Authentication Code made with a key known to both the sender and receiver.

In 1 we assume a common secret key, and that's the most classic use of a MAC; but extracting the common secret key from any receiver breaks the whole security.

In 2, that problem is solved by using keys unique to each receiver, derived from a master key and a device identifier. That's a most common key management technique for Smart Cards. Something similar to the following illustrative example may have been used for software updates in the field of pay TV:

At manufacturing, each receiver device gets a public consecutive serial number $j$, starting from $j_0$, and a (so-called diversified) secret key $K_j=\operatorname{HMAC-SHA-256}(K,j)$ where $K$ is a master secret key.
Each message $M$ (firmware update) is hashed to $H=\operatorname{SHA-256}(M)$, and it is broadcast

the length of $M$
$M$ (perhaps with a version number at some fixed offset)
the concatenation of all the $\operatorname{HMAC-SHA-256}(K_j,H)$ truncated to $b$ bits, in increasing order of $j$ (which can be computed from $K$, $j$, and $H$).

Each receiver

gets the length of $M$, and checks it is within allowable bounds
gets $M$ (perhaps checking the version number is higher than the current version; this avoids replay)
computes $H=\operatorname{SHA-256}(M)$
skips $(j-j_0)\cdot b$ bits (where $j_0$ is the first serial number)
gets the next $b$ bits
checks that against $\operatorname{HMAC-SHA-256}(K_j,H)$ truncated to $b$ bits
only then proceeds to use $M$.

Security trivially follows from the PRF properties of HMAC-SHA-256, and collision resistance of SHA-256; but a practical issue is the bandwidth used.

In 3, both security and bandwidth issues are solved, based on a shared time reference. A chain of keys is set up at initialization time, that is revealed link per link by the broadcaster, and verifiable by the receivers. A message is broadcast authenticated by a MAC per one of these keys. Receivers ensure the message is received soon enough that the key can be known only by the broadcaster, and authenticate the message later when that key is revealed.

Assume broadcaster and receivers know the number $t$ of time units (say minutes) elapsed since a reference, as an integer, with a cumulated uncertainty significantly below $\pm1$ unit between broadcaster and any receiver, accounting for their cumulated uncertainty and propagation delay.

Setup (by the broadcaster)

choose the initial time $t_0$ for first use of the system;
choose a large parameter $n$; the system will be usable up to time $t_0+n-3$;
randomly choose the master 256-bit secret $K_n$;
compute $K_j=\operatorname{HMAC-SHA-256}(K_{j+1},0\|j)$ for $j$ going down from $n-1$ to $0$, and store some of the $K_j$ (say, for $j\equiv0\bmod2^{16}$, in order to be able to recompute any $K_j$ with less than $2^{16}$ HMAC);
when a device is manufactured, and that's at $t_1\ge t_0$, compute $g=t_1-t_0$ and setup the device with the trusted pair $(K_g,g)$;

Broadcast

in order to broadcast message $M$, compute and broadcast $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ with $j=3+t_2-t_0$, where $t_2$ is the time of that broadcast, with $t_2\ge t_1\ge t_0$;
broadcast the associated $M$ itself at any time, with something to link it to the $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ that has or will be broadcast;
broadcast $K_j\|j$ in clear not earlier than time $t_0+j$ (and soon after that), perhaps for all $j$, or when use has been made of $K_j$ to authenticate a message, or/and at least once in a while (say, when $8$ time periods have elapsed since the last broadcast of $K_j\|j$);

Reception

when a receiver gets an alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$, it checks that $j+t_0-3$ is at least the current time; only if that check succeeds does the receiver accept that alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ (and buffers it until the corresponding $K_j$, and $M$, are known);
when a receiver gets an alleged $K_j\|j$, and $j>g$, the new alleged $K_j$ is checked against the trusted pair $(K_g,g)$ by way of $j-g$ iterations of the recurrence relation $K_i=\operatorname{HMAC-SHA-256}(K_{i+1},0\|i)$ with $i$ going down from $j-1$ to $g$; if and only if that checks succeeds, the trusted pair $(K_g,g)$ is atomically set to $(K_j,j)$;
a received message $M$ is accepted by a receiver when and if

an associated alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ has been accepted;
and $K_j$ is available and trusted; that is, $j\le g$ and $K_j$ can be computed from $(K_g,g)$ by way of $g-j$ iterations of the recurrence relation $K_i=\operatorname{HMAC-SHA-256}(K_{i+1},0\|i)$ with $i$ going down from $g-1$ to $j$;
and the recomputed $\operatorname{HMAC-SHA-256}(K_j,1\|M)$ is as alleged.

Protection against replay, or playing messages out of order, can be easily added. That's very similar to: Perrig, Canetti, Briscoe, Tygar, Song, TESLA: Multicast Source Authentication Transform (Internet Draft, 2000), and perhaps earlier work that I failed to locate.

Drawbacks include:

receivers must be able to maintain or obtain a trusted time reference, which is hard in practice;
there's a latency a few time the uncertainty the receivers have on time, and that will increase over time if the trusted time is maintained my a local oscillator;
a receiver will have to perform several HMAC computations before being able to authenticate messages after the the link (or its computation capacity) was interrupted, in proportion of the duration of the interruption.

All the aforementioned drawbacks are good reasons to use a signature scheme instead of symmetric cryptography:

Virtually any 32-bit CPU for sale now, and many 8-bit CPUs, have enough resources to check an RSA or Rabin signature in time negligible compared to the duration of a software upgrade.
Signature is intrinsically immune to side channel attacks on the receivers, which has the potential to leak any secret material like $K_j$.
The size overhead is constant, and modest (crosspoint is just above 2 devices if we use signature with message recovery, like 24 if we do not).


Is it possible for an element to be swapped with itself in RC4?


What are the major flaws and limitations of this hash-based stream cipher design?

Are there any fundamental flaws?

The construction itself is secure for a good H. It's close to what many stream ciphers use internally. E.g. chacha has an H that hashes a 256-bit key, a 64-bit nonce and a 64-bit counter to get 512 bits of output.

  Would it make sense to use a longer key?

Yes, if you want more brute force resistance, since finding a preimage is not enough to find the key, if it leads to different values for other counter values.

  Under what circumstances would doing H(C + K + C) instead of H(K + C) make the algorithm more secure?

If your H was vulnerable to length extension attack (e.g. SHA-256) and the counter was variable length, H(K + C) would not be secure, but H(C + K + C) might. However, with a constant sized C, I can't think of a reason to use H(C + K + C).

  I intend to use Skein, [...]

Then shouldn't you use the stream cipher construction from the Skein paper (pdf, section 4.10)?


Is it possible to create an open-source SecurID?

The best we can do today, in matter of token similar to SecurID (that is with the restriction that the authenticating value produced by the token is keyed-in by a human), is

open-source software on the verifier side, provided that

we accept that there is a secret key on that side
or we have some communication link to the token able to transfer more data than a normal human can do pressing buttons on the token

a public specification for the token, with open-source software and hardware

except for the heart of the cryptographic function used, implemented in a device with physical security such as a Smart Card IC
or if we accept a sizable residual risk that one particular security token could be cloned by a resourceful adversary that gets physically hold of it.

We have to distinguish open-source verifier from without secrets on the verifier's side, and three variants of the later.

It would possible to create a SecurID-like system with open-source verifier. In fact, the security of modern SecurID, or any cryptography following the second Kerckhoffs's principle, is supposed not to depend on any secret in the algorithm itself, but rather on how well the key is kept secret.

However, SecurID-like systems have the requirement that communication from the token is by keying-in short messages, and that is clearly antagonist to having a public method to check a token and no communication to the token: it would be enough to enumerate the possible answers to find an acceptable one.

With the addition of communication to the token with sizable bandwidth (e.g. a 2-D barcode read by the token with a camera, or just an animation on the screen read by photodiodes on the token), that is possible (e.g. make the token decipher the challenge sent RSA-enciphered by the authenticator). I remember seeing, well over a decade ago, a device (perhaps named "La grenouille") that I thought was doing just that (with photodiodes).

If communication to the token is limited to few bits (e.g. using a keyboard on the token), I doubt there is a solution.

As to open-source token: that is hard. The algorithms used by the token can and should be public, but there has to be some secret key in the token. And cloning the token is part of the complete threat model.

Currently it is unheard-of that a physical device with a fully open design holds any secret key tightly secret, facing a resourceful adversary able to manipulate the device. All Common Criteria evaluation of security devices like Smart Cards or HSMs assume some level of secret in the design.


Does maximum length of CN in a x509 cert include the length of the OIDs?

They are separate fields. Their lengths, from the very same RFC:

ub-pseudonym INTEGER ::= 128

ub-postal-code-length INTEGER ::= 16

If x500UniqueIdentifier is OID 2.5.4.45 then it is a bit-string which isn't constrained in length (afaik).

Both the Subject and the Issuer fields are instances of RelativeDistinguishedName (section 4.1.2.4) and are of SIZE (1..MAX)

Appendix B says that:

  MAX indicates that the upper bound is unspecified.    Implementations
  are free to choose an upper bound that suits their    environment.

So while the definition suggests that Subject can be as large as you want it to be, it also suggests that it may well be constrained by your particular implementation.


How can I convert a DER ECDSA signature to ASN.1?

Disclaimer: I don't know Javascript and I do not practice BouncyCastle. However, I do know Java, and ASN.1.

ASN.1 is a notation for structured data, and DER is a set of rules for transforming a data structure (described in ASN.1) into a sequence of bytes, and back.

This is ASN.1, namely the description of the structure which an ECDSA signature exhibits:

ECDSASignature ::= SEQUENCE {
    r   INTEGER,
    s   INTEGER
}

When encoded in DER, this becomes the following sequence of bytes:

0x30 b1 0x02 b2 (vr) 0x02 b3 (vs)

where:

b1 is a single byte value, equal to the length, in bytes, of the remaining list of bytes (from the first 0x02 to the end of the encoding);
b2 is a single byte value, equal to the length, in bytes, of (vr);
b3 is a single byte value, equal to the length, in bytes, of (vs);
(vr) is the signed big-endian encoding of the value "$r$", of minimal length;
(vs) is the signed big-endian encoding of the value "$s$", of minimal length.

"Signed big-endian encoding of minimal length" means that the numerical value must be encoded as a sequence of bytes, such that the least significant byte comes last (that's what "big endian" means), the total length is the shortest possible to represent the value (that's "minimal length"), and the first bit of the first byte specifies the sign of the value (that's "signed"). For ECDSA, the $r$ and $s$ values are positive integers, so the first bit of the first byte must be a 0; i.e. the first byte of (vr) (respectively (vs)) must have a value between 0x00 and 0x7F.

For instance, if we were to encode the numerical value 117, it would use a single byte 0x75, and not a two-byte sequence 0x00 0x75 (because of minimality). However, the value 193 must be encoded as two bytes 0x00 0xC1, because a single byte 0xC1, by itself, would denote a negative integer, since the first (aka "leftmost") bit of 0xC1 is a 1 (a single byte of value 0xC1 represents the value -63).

I insist on these details because my guess is that it is what the Javascript code does incorrectly. The Javascript code invokes a method called toByteArrayUnsigned; that name is evocative of conversion to an unsigned representation (i.e. always positive, even if the first bit is a 1), and that's wrong for DER. I invite you to save the raw signature in a file and decode it "by hand" to see if it matches the fine details of ASN.1 encoding, as explained above (the openssl asn1parse command may help, too).

(If my guess is right, you should have a probability of about 1/4 of getting a correct signature nonetheless -- when the values $r$ and $s$ happen to be short enough to have a high bit set to 0 when using unsigned encoding, i.e. a situation where the bug is benign.)