/**
  */
object Krypto {

  def teiler(n:BigInt) : List[BigInt] = {
    var t:List[BigInt] = List()

    for (i:BigInt <- BigInt(1) to n) {
      if ((n mod i) == BigInt(0)) {
        t = t.:+(i)
      }
    }
    t
  }

  def order(n:BigInt, q:BigInt) : BigInt = {
    val t = teiler(q - 1)

    for (i <- t) {
      if (n.modPow(i, q) == BigInt(1)) {
        return i
      }
    }
    -1
  }

  def orders(q:BigInt) : List[(BigInt, BigInt)] = {
    var t:List[(BigInt, BigInt)] = List()

    for (i:BigInt <- BigInt(1) until q) {
      val x = order(i, q)
      t = t.:+((i, x))
    }
    t
  }

  def primitives(q:BigInt) : List[(BigInt, BigInt)] = {
    orders(q).filter(_._2 == (q-1))
  }

  def units(q:BigInt) :List[BigInt] = {
    var t:List[BigInt] = List()
    for (i:BigInt <- BigInt(2) until q) {
      if (q.gcd(i) == BigInt(1)) {
        t = t.:+(i)
      }
    }
    t
  }

  def divides(d : BigInt, n : BigInt) = {
    (n mod d) == BigInt(0)
  }

  def ld(n : BigInt) : BigInt = {
    ldf(2, n)
  }

  def ldf(k : BigInt, n : BigInt) : BigInt = {
    if (divides(k, n)) k
    else if ((k*k) > n) n
    else ldf(k + 1, n)
  }

  def factors(n : BigInt) : List[BigInt] = {
    if (n == BigInt(1)) {
      return List()
    }
    val p = ld(n)
    p :: factors(n / p)
  }

  def euler(n : BigInt) : BigInt = {
    val list = factors(n)
    val list2 = list.distinct

    var euler:BigDecimal = BigDecimal(n)

    for (p <- list2) {
      euler = euler * (1 - 1/BigDecimal(p))
    }
    euler.toBigInt()
  }

  def half(n:BigInt) : BigInt = {
    n >> (n.bitLength / 2)
  }

  def solve(p:BigInt, q:BigInt) : (BigInt, BigInt) = {
    for (a <- BigInt(1) to BigInt(1000)) {
      for (b <- BigInt(1) to BigInt(1000)) {
        if (a * p - b * q == BigInt(1)) {
          return (a, b * (-1))
        }
        if (b * q - a * p == BigInt(1)) {
          return (a * (-1), b)
        }
      }
    }
    (0, 0)
  }
}



/**
  */

class ElGamal(q:BigInt, keyA:BigInt, keyB:BigInt) {
  var a = Krypto.primitives(q).head._1
  val ya = a.modPow(keyA, q)
  val yb = a.modPow(keyB, q)

  def getA = a
  def setA(newa : BigInt) = {
    a = newa
  }

  def encryptA(m:BigInt, r:BigInt) : (BigInt, BigInt) = {
    val message = m * yb.modPow(r, q) mod q
    val ar = a.modPow(r, q)
    (message, ar)
  }

  def decryptA(m:BigInt, ar:BigInt) : BigInt = {
    (m * ar.modPow(q - 1 - keyB, q)) mod q
  }

  def encryptB(m:BigInt, r:BigInt) : (BigInt, BigInt) = {
    val message = m * ya.modPow(r, q) mod q
    val ar = a.modPow(r, q)
    (message, ar)
  }

  def decryptB(m:BigInt, ar:BigInt) : BigInt = {
    (m * ar.modPow(q - 1 - keyA, q)) mod q
  }

  override def toString: String = String.format("q = %s, a = %s, ya = %s, yb = %s", q.toString(), a.toString(), ya.toString(), yb.toString())
}




/**
  */
class Rabin (p : BigInt, q : BigInt) {
  val publicKey = p * q

  def getPublicKey = publicKey

  def encrypt(m : BigInt, key:BigInt) : BigInt = {
    ((m << m.bitLength) + m).modPow(2, key)
  }

  def decrypt(m : BigInt) : ((BigInt, BigInt, String), (BigInt, BigInt, String), (BigInt, BigInt, String), (BigInt, BigInt, String)) = {
    val solve = Krypto.solve(p,q)
    val a = solve._1
    val b = solve._2
    val r = m.modPow((p + 1) / 4, p)
    val s = m.modPow((q + 1) / 4, q)
    val x = (a*p*s + b*q*r) mod publicKey
    val y = (a*p*s - b*q*r) mod publicKey

    ((x, Krypto.half(x), x.toString(2)), (y, Krypto.half(y), y.toString(2)),
      ((x * -1) mod publicKey, Krypto.half((x * -1) mod publicKey), ((x * -1) mod publicKey).toString(2)),
      ((y * -1) mod publicKey, Krypto.half((y * -1) mod publicKey), ((y * -1) mod publicKey).toString(2)))
  }

  override def toString: String = String.format("publicKey = %s", publicKey.toString())
}

/**
  */
class RSA (p: BigInt, q: BigInt, e: BigInt){
  val n: BigInt = p * q
  val phi: BigInt = (p - 1) * (q - 1)
  if (e.gcd(phi) != BigInt(1)) {
    throw new IllegalArgumentException("gcd(e, phi) != 1")
  }
  val d: BigInt = e.modInverse(phi)

  override def toString: String = String.format("p = %s, q = %s, e = %s, d = %s, phi = %s, n = %s", p.toString(), q.toString(), e.toString(), d.toString(), phi.toString(), (p * q).toString())
}

object RSA {
  def decrypt(d: BigInt, m: BigInt, n: BigInt): BigInt = {
    m.modPow(d, n)
  }

  def encrypt(e:BigInt, m: BigInt, n: BigInt): BigInt = {
    m.modPow(e, n)
  }

  def text2Number(m: String): BigInt = {
    BigInt.apply(m.getBytes)
  }

  def number2Text(m: BigInt): String = {
    new String(m.toByteArray)
  }
}
import scala.collection.immutable.Range.BigDecimal

/**
  */
class SteamCipher (bit:Int, var key:BigInt, cipher: (BigInt) => BigInt ) {
  def next : BigInt = {
    key = (BigInt(2).pow(bit) - 1) & key
    key = (BigInt(2).pow(bit) - 1) & cipher(key)
    key
  }
}

object SteamCipher {
  def test(mem:BigInt) : BigInt = {
    var ret = mem << 1
    val next = mem.testBit(3) ^ mem.testBit(2) ^ mem.testBit(1) ^ mem.testBit(0)
    if (next) {
      ret = ret + BigInt(1)
    }
    ret
  }
  def test2(mem:BigInt) : BigInt = {
    var ret = mem << 1
    val next = mem.testBit(2) ^ mem.testBit(0)
    if (next) {
      ret = ret + BigInt(1)
    }
    ret
  }
}