User:Cspan64/Sandbox

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Userboxes

This user comes from Germany.

This user comes from Baden-Württemberg.

Wikipedia:User_page

Key generation

To allow for decryption, the modulus used in Blum-Goldwasser encryption should be a Blum integer. This value is generated in the same manner as an RSA modulus, except that the prime factors $(p,q)$ must be congruent to 3 mod 4. (See RSA, key generation for details.)

Alice generates two large prime numbers $p\,$ and $q\,$ such that $p\neq q$ , randomly and independently of each other, where $(p,q)\equiv 3$ mod $4$ .
Alice computes $N=pq$ .
Alice can also precompute now $q^{-1}\,$ and $p^{-1}\,$ , so that

$ap+bq=1$ (Bezout's identity) using the extended euclidean algorithm.

The public key is $N$ . The secret key is the factorization $(p,q)$ .

Message decryption

Alice receives $(c_{0},\dots ,c_{L-1}),y$ . She can recover $m$ using the following procedure:

Using the prime factorization $(p,q)$ , Alice computes $r_{p}=y^{((p+1)/4)^{L}}~mod~(p-1)$ and $r_{q}=y^{((q+1)/4)^{L}}~mod~(q-1)$ .
Compute the initial seed $x_{0}=q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q}~{mod}~N$
From $x_{0}$ , recompute the bit-vector ${\vec {b}}$ using the BBS generator, as in the encryption algorithm.
Compute the plaintext by XORing the keystream with the ciphertext: ${\vec {m}}={\vec {c}}\oplus {\vec {b}}$ .

Alice recovers the plaintext $m=(m_{0},\dots ,m_{L-1})$ .

Inversion of 3 x 3 matrices

The cofactor equation listed above yields the following result for 3 x 3 matrices. Inversion of these matrices can be done quite easily as follows:

    $A^{-1}={\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\\\end{bmatrix}}^{-1}={\frac {1}{|A|}}{\begin{bmatrix}ei-fh&ch-bi&bf-ce\\fg-di&ai-cg&cd-af\\dh-eg&bg-ah&ae-bd\end{bmatrix}}$