i think it's on the sensor. but first a few points of clarification:
to check for dirt on sensor or lens the aperture of the lens is closed down all the way to f22. with aperture wide open the dirt cannot be seen, with aperture closed to f22 it usually appears as darkish spots (with no sharp outline) from dirt on the lens, and as very dark dots or lines (with sharp outline) from dirt on the sensor. that's why i think it's on the sensor.
changing focus doesn't really change the appearance of the dirt. i think by "changing focus" you actually meant "changing aperture"?
the sensor is very delicate, and should NEVER be touched with anything!! therefore usually it is cleaned only with a manual air blower. if this isn't enough, to further clean the sensor requires special tools: a dedicated special swab exactly the size of the sensor and a special fluid. it can be done at home, but it needs to be done correctly and with the correct swab for the specific sensor size. most people bring the camera to the service for doing that, because any error will damage the sensor. if you want to do it yourself, please watch videos about it that explain it in detail.
another small note: usually the lens is taken off and cleaned on the backside. "opening the lens and cleaning from the inside" means disassamling it with special screwdrivers and taking out the individual lens elements for cleaning. i guess you meant cleaning from the backside.