grocid

In index calculus, the main problem is to represent powers of $g$ in a predefined prime-number basis. We are interested in unravel $x$ from $h = g^x\bmod p$.

**Normal approach**

First, we find some offset $hg^j = g^{x+j}\bmod p$ such that the factorization is $B$-smooth.

Using the prime-number basis $(-1)^{e_1}2^{e_2}\cdots$, generate a corresponding vector

$$
\mathbf y = \begin{pmatrix}1 & 0 & 3 & 0 & \cdots & 1\end{pmatrix}

grocid

Keybase proof

I hereby claim:

• I am grocid on github.
• I am grocid (https://keybase.io/grocid) on keybase.
• I have a public key ASBq9r-CvBBtXW9zYFXv2x1lndNeNYboHqoPaOjoqaYnOwo

To claim this, I am signing this object:

grocid

p = 3122882963  # 32-bit safe prime
#p = 13019428505045596307
R = IntegerModRing(p - 1)
Field = GF(p)
g = Field(2*3*5*7*11*17*19)
exp = 1234562364  # just some bang-on-the-keyboard exponent
h = g**exp
B = 199  # there are 45 primes < B

# find basis using approximation

grocid

# not an exhaustive list

nsurlsessiond "icloud sync"
fseventsd "macos file system events"
WindowServer "macos windows"
DisplayLinkManager "macos driver"
configd "macos dynamic configuration"
displaypolicyd "macos process"
CommCenter "macos keychain"
kernel_task "macos kernel"

grocid

def decrypt(exp, num, key):
    out = ""
    #num = int(num.encode("hex"), 16)
    i = int(log(num, exp))
    gg = exp**i 
    for j in range(0, i):
        if num / (gg + (-1)**i) > 0:
            out += "1"
            num -= (gg + (-1)**i)
        else:

grocid

""""
  4xy-1 | (x^2-1)^2 => y=x/4 unless we are in an extension field, which we are not.
""""
n = 23720866119974556285499901115689003965870062415206976810347819237644601145156308010203892609342945656883476310167029902385520978020835798935418774122088743409344583205326082037405769853636631064670984329276209889276307194165918070287252337433800299063479153068493458044205347702215616236648930857109340873805820266107552367844699338756641947355949680889027641144279462588126121841761859294448270964317934355623676435109416588236921615213152873180239772584171588461799522067239177136763647909153956526409315765532261432546716239262006754237909209804472665795149517854683809713558307958915912536026551883790672064505068901692322819597454241576968425661920496216252245915367408714107854530076631226031643799754269823349670271093596146221248359037217509346808489337994529151192634142192912893705076606683926370989440933051535086264397543467216721178431989391429073956147048837302721277173237002483499187779528059405621557495847549

grocid

pubkey = 3415775651990117231114868059991823731694168391465118261123541073986397702947056759501589697018682285283905893102019391953165129250445987511496328390478214156138550568081360884795196720007402795178414072586445084589188812271144227913976270609786532206307549154139514246177504313696905220271023590900584622193476455815728425827517096143262953674043805121028581660274394493861460258597130188538332977679416970808454282017991307383835356188698891323239771333178860346825972405652914210954631134409600833327693593543421410732434281694454355747008933885889869077937880862749049074740126067215284910788706518425606114203333939656875871818894784079170292840540681948732880660003000926906333894065117345867196506856521542472349855590932301830372695420851264943795112040150205561483289746364835891125359307397506516272039186039783992620965800450343112765502550149168357851547665186618429181796721954012847077634388652598794182315250366936611355658686688939934516900009808518223359241944137277154786476218874224865037819222158

grocid

import gmpy
import gmpy2
from fractions import gcd

def dec(n):
	return hex(int(n))[2:].rstrip("L").decode("hex")

a = 6129045310763021790856152782924435339394912490651057968119749104677844846162024187811538414115989381648951838817446260921271338817469089315786401389425432101937455179482722831943870567609546871302790334453123063844667446129248579853099572319467917572203259488663792717230663614348203087634000738716846236453
b = 21004857544287019239408534531449948348159609726790908306974348947117991714054409869257133081929914591459899655908141325761521904936043948049419550774861506510243817009663859463393778639031555475954933858324795455033652926443512596678184253204623932432419421335015720413437778576835470802621470778941669835875
c = 2972136493183965344114007674609993597713072794880759772984437641427657180110495134274004221892375842569585334922918679459749045191061404192934156403495451739226616965840615191049809949608090285920936868955012790946030557079305959536719856549904210788958874172140095396604584707828

grocid

a = 38555641240142650191590665
b = 23359130730155144478219192
c = 23880474167586014776570576
d = 42898493346005241877878759
e = 44617407039071303012851645

X = (c-d)^2-(d-e)*(b-c)
Y = (b-c)^2-(c-d)*(a-b)

mod = gcd(X,Y)

grocid

data = """z:$6$AEqLtEqq$1ojEoCgug5dzqeNfjGNE9p5SZFwIul8uOFp9vMZEz50oiUXOVFW3lw1S0fuvFY5ggi5CfbfoWaMDr2bvtSNRC/:17930:0:99999:7:::
a:$6$9Eg69bYI$q75YWUVWb4MYzkcExXukpt.VJ3fX458iZJm1ygpTLwX.CgroHpmeSG88By.zQmKyOHCvBHoA0Q001aBqbkVpg/:17930:0:99999:7:::
x:$6$5TF0Txe3$APSNzUSjFmMbsmrkCS9qE84qfu4AI2dNEjqm2PRKgSjncBTI4lECXofQ8abdAtYX6tST6FGCgOdvLlDYQTCJx0:17930:0:99999:7:::
q:$6$I3iqZL0m$nxHWvcLz7lg/ZKoKfX9dq5k0uqkOtKgLdyREAQxQkfPkVvbNHPfQaoCFfnXl1BoX1vgOcEDghVPvfRUrs6dGp1:17930:0:99999:7:::
l:$6$n8iJWaW/$M1Od8seiEL6h3L.egHubBYAk.cd8/LUctESIm69/r.gvP0eqabusN5/D1rNu1qDHOkgRpHf8PWGSb8zoxrgrp1:17930:0:99999:7:::
v:$6$GatagTHS$I1UfNfn3NGP5Vre0z7s3DGqFpjN5Pw2XhAHSw6ZSMwaMAsf8IteFedXovNlHLuIXvR9ezeya89XEOq2We7CcW1:17930:0:99999:7:::
e:$6$ZO6YiExi$7DBV0zMIqf8iy.zVTL7gbHetCmJ3LL4ROEYG/UME4Tmym82vZYkFWjiNpCGapvF83QNJKFJOjkhXMgFLfkhza.:17930:0:99999:7:::
f:$6$HXoF2OZ1$onkVfp52IRdd2OipQv3rPPsGr7QradAFTFnmXv5c9xkGy4xcgJFkoaSJzMQCtfWuU2FQ3BN3lyL47SyoIoPmy0:17930:0:99999:7:::
b:$6$I9Uq9PRG$euVEYx5TR2lUFe/k7s0e8us8xgl7j/cbiYRnvba.