CUPIC

[Globemaker]

Cryptosystem Using Private Inverse Coefficient : CUPIC
by Alan C. Folmsbee
March 8, 2011 Rev. 95

Research this:
How to make public the square TT,
but keep inverse of T SECRET!

Choose a padding number T, to be squared to become TT
Choose secret primes j and k
public modulus n = jk
publish n
publish Z = TT mod n
Secretly calculate coefficient " T inverse " = " 1/T "
private 1/T mod j or
private 1/T mod k

m is message
c is ciphertext
ENCRYPT
c=sqrt(Zmm) mod n
DECRYPT
m = (1/T mod k) * (sqrt(cc) mod n)

ABSTRACT without modulus
$$$$$$$$$$$$$$$
c=sqrt(TTmm)
cc=TTmm
cc/TT = mm
m=sqrt(cc/TT)
m = 1/T * sqrt(cc) ...INVERSE COEFFICIENT 1/T
$$$$$$$$$$$$$$$

maybe...
m = sqrt(cc) mod n * 1/T mod k

Use the fact: "if a is a residue (mod n) then a is a residue (mod p^k)
for every prime power dividing n. From

http://en.wikipedia.org/wiki/Quadratic_residue "
.......................................................

Example non-modular versions of cryptosystems
CUPIC:
m is message
T INVERSE is secret
TT IS PUBLIC
c=sqrt(TTmm)
cc=TTmm
cc/TT = mm
m=sqrt(cc/TT)
m=sqrt(cc) * 1/T (T INVERSE IS SECRET)

EXAMPLE
T=3 m=11
c=sqrt(9*121) = sqrt 1089 = 33
m=sqrt(33*33/9) = 1/3 * sqrt (1089) = 11
.....................................
rabin
c =mm PUBLIC COMPOSITE MODULUS pq
m=sqrt c SECRET PRIME MODULI : p and q
......................................
rsa
c=m^e PUBLIC EXPONENT : e
m=c^d SECRET EXPONENT : d
.................................
CUPIC
c=sqrt mmTT PUBLIC PADDING TT
m=(sqrt cc) * 1/T SECRET FACTOR : T INVERSE
.............................
TT PADDING IS PUBLIC, T INVERSE IS PRIVATE

CUPIC example with tiny numbers REV 95

padding number T=11, to be squared to become TT=121
Choose secret primes j and k = 5, 7
public modulus n = jk =35
publish n=35
publish TT mod n = Z = 16
Secretly calculate coefficient " T inverse " = " 1/T "
private 1/T mod j or
private 1/T mod k
11 mod 7 ==4
inv(4) mod 7 == 2
because 2 x 4 = 8 ==1 mod 7

m is message = 10
c is ciphertext
c=sqrt(Zmm) mod n
c = sqrt 1600 mod 35 = 5

maybe...
m = sqrt(cc) mod n * 1/T mod k
m= 5 * 2 = 10
YES!
.........................
If you cannot factor n=jk then it is hard to take TT mod n and
calculate T inverse mod k. Collaborators welcome.

[Globemaker]

Additional notes on CUPIC

I am hoping a collaborator will help overcome the flaw where
the security is defeated when someone calculates the
inverse of Z == TT mod n
n=jk
A two public key algorithms of Rabin and RSA allow strangers
to encrypt their own messages but they cannot even decrypt
them. Combined information is made public, but it cannot be
separated out. You could contribute one more factor into Z or n
to perfect this algorithm by making it difficult to calculate the
inverse of Z, inv(Z).

Encrypt
c == sqrt(Zmm) mod n

Decrypt
cc == Zmm mod n
mm == cc/Z mod n
m == sqrt(inv(Z) mod n) * sqrt(cc) mod n

Under construction...

[Bryan]

Globemaker <alanfolms...@cabanova.com> wrote:
> Cryptosystem Using Private Inverse Coefficient : CUPIC
> by Alan C. Folmsbee
> March 8, 2011 Rev. 95
>
> Research this:
> How to make public the square TT,
> but keep inverse of T SECRET!
>
> Choose a padding number T, to be squared to become TT
> Choose secret primes j and k
> public modulus n = jk
> publish n
> publish Z = TT mod n
> Secretly calculate coefficient " T inverse " = " 1/T "
> private 1/T mod j or
> private 1/T mod k
>
> m is message
> c is ciphertext
> ENCRYPT
> c=sqrt(Zmm) mod n

That doesn't work at all. Alan, you seem to be missing the basics of
public-key cryptography. Encryption must be efficient given the
published parameters, while decryption is intractable unless one also
knows the private parameters. The scheme here fails both ways: Given
the public parameters and the message, we cannot tractably compute the
ciphertext, but given the public parameters and the ciphertext, we can
efficiently recover the plaintext.

So if it's wrong both ways for encryption, does it work for signature?
Alas, no. From the public parameters and one pair (m, c), we can
efficiently compute the mod n square root of Z. I'll use '==' to
denote modular congruence:

c == sqrt(Zmm) mod n

c == sqrt(Z) * sqrt(mm) mod n

c == sqrt(Z) * m mod n

c * 1/m == sqrt(Z) mod n

Modular inverse is efficiently computable, so from the given we can
solve for sqrt(Z) and break the system.

--
--Bryan Olson

[Bryan]

Globemaker <alanfolms...@cabanova.com> wrote:
> Additional notes on CUPIC
>
> I am hoping a collaborator will help overcome the flaw where
> the security is defeated when someone calculates the
> inverse of Z == TT mod n

To overcome the flaws, throw it out.

> n=jk
> A two public key algorithms of Rabin and RSA allow strangers
> to encrypt their own messages but they cannot even decrypt
> them.

Yes, we have public-key cryptosystems based on the modular root
problem which stand to this day. RSA was the first; then Rabin brought
the security to provably equal to the difficulty of factoring; then
Rabin-Williams restored 1-to-1 elegance. Those schemes are worth
studying.

--
--Bryan Olson

[Globemaker]

Thanks for your comments, Brian. I have not yet abandoned this
attempt, but that may happen, later.

[Bryan]

I wrote:
> Yes, we have public-key cryptosystems based on the modular root
> problem which stand to this day. RSA was the first; then Rabin brought
> the security to provably equal to the difficulty of factoring; then
> Rabin-Williams restored 1-to-1 elegance. Those schemes are worth
> studying.

Also see Bellare and Rogaway's work on "Exact Security" and OAEP.
Modern hashing and formatting is particularly important when using the
even-public-exponent variant of RSA.

--
--Bryan Olson

[Globemaker]

Abandoning this attempt.

Bryan is right, so I am abandoning this attempt at a public key scheme
because the goals are contradictory where:
Z == TT mod jk (goal 1) where no inverse of Z exists mod jk
FOR NON-EXISTENCE OF INVERSE OF Z:
Z == 0 mod jk goal 2
so both goals cannot be accomplished together.
End of attempt.

[Bryan]

Thanks for saying I was right when I said your scheme doesn't work,
but this new stuff leaves me even more baffled. Z is zero mod jk? You
are correct that zero has no multiplicative inverse, but didn't we
learn that in third grade?

What did you think your "padding number T" should be, so that TT == Z
== 0 mod jk? Remember that in your scheme you "Choose secret primes j
and k".

--
--Bryan Olson

[Bryan]

I wrote:
> Also see [...]

Poor form as it is to follow-up one's own reply, and all the worse
that I'm following-up myself following-up myself, I'll point out
writing on the state-of-the-art in public key signatures based on the
modular square/square-root problem, by this group's old friend Dan
Bernstein.

Here's a link that currently works:

http://cr.yp.to/sigs/rwsota-20080131.pdf

Or search up 'rabin signature bernstein'.

--
--Bryan Olson