ATTiny85: Invalid device signature

Hi, I just bought a bunch of ATTiny85's from ebay and I want to program them. I am using an Arduino Mega as the ISP, but when I try to program it I get this error:

avrdude: Device signature = 0x000000
avrdude: Yikes! Invalid device signature.
Double check connections and try again, or use -F to override
this check.

Error while burning bootloader.

The markings on the Tiny's say "1605", which I guess means May 2016. I guess they might be fake, but I am not sure how to test this. I tried to test the resistance between vcc and ground on the microcontroller, but it didn't give me a reading, and that kinda scares me.

I have checked all my cables, and I have a 10 uF capacitor on the Mega's resetpin (to ground).

I tried switching the tiny for another one, but got the same result. I unfortunately do not have any other arduino I can use as an ISP in case the Mega is not suitable.

Any help would be greatly appreciated as I am kinda furious at these microcontrollers right now.

Have you uploaded the ArduinoISP sketch to the Mega BEFORE hooking anything else up and burning bootloader?
Are the MOSI/MISO/SCK pins the same numbers on the Mega?

I just took off all the wires and uploaded the blink sketch, and then the ArduinoISP sketch again, but no luck.

I have no idea what numbers the MOSI, MISO,SCK pins are on the mega, would I have to change the pins from 10-13 that are used in the sketch to something else since I am using the mega instead of the uno?

Thank you sooooo much, INTP!! I switched the pins to the correct MISO/MOSI/SCK pins and it worked!
Namely, pin 52 instead of 13, 50 instead of 12 and finally 51 instead of 11. pin 10 is still pin 10.

On an unrelated note, my MBTI-type is INTP as well:)